The beauty of creative problem solving

I read about a question that was given to a programmer in an Oracle Interview. I hope he did not get the job, because he simply posted his question on Stack Overflow, but the question itself, looked like a very interesting one.

How would you divide a number by 3 without using *, /, +, -, %, operators?

The question, as given on Stack Overflow.

Think about this question for a while. Perhaps your favourite programming language has a built in solution. Well, C does, so that would make the job as easy as using div:

The div() function computes the value numerator/denominator and returns the quotient and remainder in a structure named div_t that contains two integer members (in unspecified order) named quot and rem.

man page of div

This is, of course, the simplest solution available. If your interviewer is trying to look at your knowledge of the language, this would be a fit solution too. I do hope however, that you won’t meet many interviewers who are looking for solutions like these.

It is more interesting to see what you actually know about algorithms and creative problem solving. That’s why someone else responded with this piece of brilliant code:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    FILE * fp=fopen("temp.dat","w+b");
    int number=12346;
    int divisor=3;
    char * buf = calloc(number,1);
    fwrite(buf,number,1,fp);
    rewind(fp);
    int result=fread(buf,divisor,number,fp);
    printf("%d / %d = %d", number, divisor, result);
    free(buf);
    fclose(fp);
    return 0;
}

This actually writes 123456 bytes to a file, which can be of course, any number you are trying to check. After that, it reads chunks of 3 bytes each, and returns the amount of times it was able to read a chunk. Therefore, it divides the original number by 3.

Of course, this is a horrible solution, but that’s fine, according to the one who posted the code, because it fits the question.

Let’s look at another creative piece of code:

#include <stdio.h>

int main() {
  int dividend = -42, divisor = 5, quotient, remainder;

  __asm__ ( "cdq; idivl %%ebx;"
          : "=a" (quotient), "=d" (remainder)
          : "a"  (dividend), "b"  (divisor)
          : );

  printf("%i / %i = %i, remainder: %i\n", dividend, divisor, quotient, remainder);
  return 0;
}

This one is creative enough to use another language into C. He decided to use assembly to solve this problem, because even assembly has division instructions built in.

An even better solution came from someone who suggested to use the Setun computer. This was a computer from Moscow that used a ternary system instead of a binary one. This allows you to do one right shift to divide a number by 3.

Obviously, the answer would be to use left and right bit shifting to replace the + and - operators, of course:

// replaces the + operator
int add(int x, int y)
{
    while (x) {
        int t = (x & y) << 1;
        y ^= x;
        x = t;
    }
    return y;
}

int divideby3(int num)
{
    int sum = 0;
    while (num > 3) {
        sum = add(num >> 2, sum);
        num = add(num >> 2, num & 3);
    }
    if (num == 3)
        sum = add(sum, 1);
    return sum; 
}

But if that is too complicated for you, and you only need a demo, you can always try this:

if (number == 0) return 0;
if (number == 1) return 0;
if (number == 2) return 0;
if (number == 3) return 1;
if (number == 4) return 1;
if (number == 5) return 1;
if (number == 6) return 2;

Published by

Robin Martijn

I am Robin Martijn, a developer and entrepreneur from the Netherlands. I was born in Rotterdam and now live in the quiet village of Brielle. I am involved in innovation developments in the field of healthcare and aviation technology. I am also chairman of the study association of the Computer Science and Engineering course in Rotterdam.

3 thoughts on “The beauty of creative problem solving”

  1. this may be cheating, but you could get the result from log(3)-log(2). technically, there was no mention of getting the log of 3 and 2.

  2. Neither of these solutions are valid the problem specifies dividing a number, not an integer. Some of these only work on natural numbers. It your second to last example you are doing right shifts on a signed number which is not defined behavior when the number is negative. Your solution is probably the worst since it is only defined over 7 of the uncountably infinite amount of numbers.

Leave a Reply to neal Cancel reply

Your email address will not be published. Required fields are marked *