Learn how to find the square of a number without using multiplication(*), division(/) or math operators(pow()).
Example
Input: 5 Output: 25
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.