Find the square of a number without using the multiplication and division operator
Given an integer, find its square without using multiplication and division operator. Also, the use of the power function from any programming language library is not allowed.
Method 1:
The idea is based on the fact that the square root of any number n can be calculated by adding odd numbers exactly n times. The relation can be expressed as:
22 = (1 + 3) = 4
32 = (1 + 3 + 5 = 9)
42 = (1 + 3 + 5 + 7) = 16
The implementation can be seen below in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <iostream> using namespace std; int findSquare(int num) { int odd = 1; int sq = 0; // convert the number to positive if it is negative num = abs(num); // add odd numbers num times to result while (num--) { sq = sq + odd; odd = odd + 2; } return sq; } int main() { cout << findSquare(8) << " " << findSquare(-4); return 0; } |
Output:
64 16
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
class Main { public static int findSquare(int num) { int odd = 1; int sq = 0; // convert the number to positive if it is negative num = Math.abs(num); while (num-- > 0) { sq = sq + odd; odd = odd + 2; } return sq; } public static void main(String[] args) { System.out.println(findSquare(8)); System.out.println(findSquare(-4)); } } |
Output:
64 16
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
def findSquare(num): odd = 1 sq = 0 # convert the number to positive if it is negative num = abs(num) while num > 0: sq = sq + odd odd = odd + 2 num = num - 1 return sq if __name__ == '__main__': print(findSquare(8)) print(findSquare(-4)) |
Output:
64 16
Method 2: Repeatedly adding a given number to the result
The idea is to repeatedly add a given number n to the result n times. For example,
Following is the C++, Java, and Python implementation of the idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#include <iostream> using namespace std; int findSquare(int num) { // convert the number to positive if it is negative num = abs(num); // stores square of the number int sq = num; // repeatedly add `num` to the result for (int i = 1; i < num; i++) { sq = sq + num; } return sq; } int main() { cout << findSquare(8) << " " << findSquare(-4); return 0; } |
Output:
64 16
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Main { public static int findSquare(int num) { // convert the number to positive if it is negative num = Math.abs(num); // stores square of the number int sq = num; // repeatedly add `num` to the result for (int i = 1; i < num; i++) { sq = sq + num; } return sq; } public static void main(String[] args) { System.out.print(findSquare(8) + " " + findSquare(-4)); } } |
Output:
64 16
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
def findSquare(num): # convert the number to positive if it is negative num = abs(num) # stores square of the number sq = num # repeatedly add `num` to the result for i in range(1, num): sq = sq + num return sq if __name__ == '__main__': print(findSquare(8)) print(findSquare(-4)) |
Output:
64
16
Method 3: Using Divide and Conquer with bitwise operators
If n is even, the square of n can be expressed as n2 = ((n/2) × 2)2 = (n/2)2 × 4.
If n is odd, the square of n can be expressed as n2 = ((n - 1) + 1)2 = (n - 1)2 + 1 + 2 × (n - 1) × 1 = ((n/2)2 × 4) + 1 + (n/2) × 4.
This is demonstrated below in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include <iostream> using namespace std; int findSquare(int num) { // base case if (num < 2) { return num; } // convert the number to positive if it is negative num = abs(num); // drop last bit from num (divide it by 2) int i = num >> 1; // if num is odd if (num & 1) { return ((findSquare(i) << 2) + (i << 2) + 1); } // if num is even else { return (findSquare(i) << 2); } } int main() { cout << findSquare(8); return 0; } |
Output:
64
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
class Main { public static int findSquare(int num) { // base case if (num < 2) { return num; } // convert the number to positive if it is negative num = Math.abs(num); // drop last bit from num (divide it by 2) int i = num >> 1; // if num is odd if ((num & 1) == 1) { return ((findSquare(i) << 2) + (i << 2) + 1); } // if num is even else { return (findSquare(i) << 2); } } public static void main(String[] args) { System.out.print(findSquare(8)); } } |
Output:
64
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
def findSquare(num): # base case if num < 2: return num # convert the number to positive if it is negative num = abs(num) # drop last bit from num (divide it by 2) i = num >> 1 # if num is odd if (num & 1) == 1: return (findSquare(i) << 2) + (i << 2) + 1 # if num is even else: return findSquare(i) << 2 if __name__ == '__main__': print(findSquare(8)) |
Output:
64 16
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)