Thursday, March 12, 2015

Adobe Question: Calculate square of a number without using arithmetic operators and inbuilt methods

Question: Calculate square of a number without using arithmetic operators like *, /, +, -. Obviously inbuilt methods like pow() can't be used.

Solution:

1: If the given number 'num' is even then:
    num = 2 * n
    so square(num) = square (2 * n) = 4 * square(n)

2: If num is odd then:
    num =  2 * n + 1
    so square(num) = square(2 * n +  1) = 4 * square(n) + 4 * n + 1

Implementation:

int square(int num)
{
if(num == 0 || abs(num) == 1)
return abs(num);

if(num < 0)
num = -num;

int half = num>>1;

if(num & 1)
return ((square(half)<<2) + (half<<2) + 1);
else
return (square(half)<<2);
}

Complexity: O(log(n))

No comments:

Post a Comment