Placement papers | Freshers Walkin | Jobs daily: Fastest way to multiply a number by 7

Search jobs and placement papers

Fastest way to multiply a number by 7

Top companies like microsoft, google asks algorithm oriented questions to test the analytical skill of the candidate. Here is one such question.

Given a number N, devise an algorithm to multiply N by 7?

        Well we obviously think that N * 7 is the answer. But it is not. Remember multiplication is a tedious process. It needs many registers and takes some time to produce the output.Therefore we have to reduce the time complexity. The interviewer looks exactly the best possible answer and let us find it now.

       The bitwise operators are very fast enough and hence our intution tells us that the answer should involve bitwise operations. We know that we can multiply a number by 8 just by left shifting the number 3 positions. So we can use it to multiply N by 7. The working method is given below.

N * 7 = N * (8 - 1)
          = N * 8 -N
N * 7 = N << 3 - N

Thus a function in C to multiply N by 7 is given below.
int mul_by_seven ( int n)
  return (n << 3) - n;

In any technical interview the interviewer tries to find out how you work out solving a problem and hence talk aloud while you think.

No comments:

Post a Comment