Find square of a number without using *, / and pow()

Learn how to find the square of a number without using multiplication(*), division(/) or math operators(pow()).

Example

Input:
5

Output:
25

Square of a number without using * / pow()

The simplest solution is to add the same number for same amount of time to get the square of that number.

const square = (n) => {
  if( n < 0) return n;
  
  let result = n;
  for(let i = 1; i < n; i++){
    result += n;
  }
  
  return result;
}
Input:
console.log(square(5));

Output:
25

Time complexity: O(n).
Space complexity: O(1).


An efficient approach which finds the square of a number in O(logn) without using *, /, or pow().

Conceptually this is how it works.

  • Create a function which recursively calls itself to find its square.
  • In each call check if the number is odd or even.
  • If it is even then call the same recursively as 4*square(n/2).
  • If it is odd then 4*square(floor(n/2)) + 4*floor(n/2) + 1 .
  • In the end return the combined result.
function square(n){
  if n === 0 return 0;
  if n is even 
     return 4*square(n/2) 
  if n is odd
     return 4*square(floor(n/2)) + 4*floor(n/2) + 1 
}

Examples:
square(6) = 4*square(3)
square(3) = 4*(square(1)) + 4*1 + 1 = 9
square(7) = 4*square(3) + 4*3 + 1 = 4*9 + 4*3 + 1 = 49

As we are not allowed to use any mathematical operators we will be using the bitwise shift operators to find the floor values.

const square = (n) => { 
  
  // Base case 
  if (n == 0)  return 0; 

  // Handle negative number 
  if (n < 0)  n = -n; 

  // Get floor(n/2) using 
  // right shift 
  let x = n >> 1; 

  // If n is odd  
  if (n % 2 != 0){
    return ((square(x) << 2) + (x << 2) + 1);
  }
  else { 
    // If n is even 
    return (square(x) << 2);
  }
} 
Input:
console.log(square(6));

Output:
36

As in the each recursive call we are reducing the number by half so,
Time complexity: O(logn).
Space complexity: O(n) considering the call stacks.