Square without Multiplication, Division & Pow Editorial

Practice Problem Link: Square without Multiplication, Division & Pow

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You are given a positive integer num. Find its square.
You cannot use the multiplication or division operator. Also the power function of any library is not allowed.

Naive Approach

The naive idea is to know that multiplication or power operation is just repeated addition. So we can add our number to itself, num number of times, to get the result.

Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Implementation

C++

int findSquare(int num) {
   	int copy = num;
	for(int i = 1; i < copy; i++) {
		num += copy;
	}
	return num;
}

Java

class Solution {
    int findSquare(int num) {
        int copy = num;
		for(int i = 1; i < copy; i++) {
			num += copy;
		}
		return num;
    }
}

Optimal Approach

The optimal approach to solve this problem is to use a Divide and Conquer Approach, along with using bitwise operators. We can use some mathematics to rewrite the original problem as:

• If x = Odd, x2 = ((x - 1) + 1)2 = (x - 1)2 + 1 + 2(x - 1) = ((x / 2)2 X 4) + 1 + (x / 2) X 4.
• If x = Even, x2 = ((x / 2)2 X 4).

These cases can be easily solved with recursion and bitwise operators as all operations requires some power of 2.

Analysis

• Time Complexity: O(log n)
• Space Complexity: O(1)

Implementation

C++

int solve(int num) {
	if(num < 2) {
		return num;
	}
	int numBy2 = num >> 1;
	if(num & 1) {
		return ((numBy2 << 2) + 1) + (solve(numBy2) << 2);
	}
	else {
		return (solve(numBy2) << 2);
	}
}
int findSquare(int num) {
	return solve(num);
}

Java

class Solution {
	int solve(int num) {
		if(num < 2) {
			return num;
		}
		int numBy2 = num >> 1;
		if((num & 1) != 0) {
			return ((numBy2 << 2) + 1) + (solve(numBy2) << 2);
		}
		else {
			return (solve(numBy2) << 2);
		}
	}
    int findSquare(int num) {
       return solve(num);
    }
}