Last Updated: 28 Jan, 2021
Calculate square of a number
Easy
Asked in company
Given an integer ‘N’, you are supposed to return the square of the given integer without using multiplication (*), division (/) or power function (pow()).
Input format:
The first line contains a single integer ‘T’ denoting the number of test cases.
Each test case contains a single line with a single integer ‘N’ denoting the given number.
Output format:
For each test case, print the square of the given number in a separate line.
Note:
You do not need to print anything; it has already been taken care of.
Constraints:
1 <= T <= 50
-10000 <= N <= 10000
Time Limit: 1 sec.
Approaches
Our first intuition is to simplify multiplication into repetitive addition.
Steps are as follows:
- Square of ‘N’ means N*N.
- This can also be written as the addition of ‘N’ to the result ‘N’ times.
- For example Square(3) = 3 + 3 + 3 = 9.
- So we will run a loop ‘N’ times and keep on adding ‘N’ to the result in each iteration.
- An edge case is when the integer is negative. We also know that the square of ‘N’ and ‘-N’ is the same, so whenever we are given a negative integer, we will convert it to a positive integer.
The idea is to basically write a perfect square in terms of a series and it turns out to be the sum of the first ‘N’ odd numbers.
square(1) = 1
square(2) = 1 + 3 = 4
square(3) = 1 + 3 + 5 = 9
square(4) = 1 + 3 + 5 + 7 = 16
An edge case is when the integer is negative. We also know that the square of ‘N’ and ‘-N’ is the same, so whenever we are given a negative integer, we will convert it to a positive integer.
Our main approach here is to use bitwise operators. Let’s take a look at even and odd numbers individually.
Firstly if ‘N’ is even:
For a number to be even it needs to be a multiple of 2. So ‘N’ can be written as 2*C, where C is an integer.
Now N^2 will be (2*C)^2 = 4*C^2.
Secondly if ‘N’ is odd:
Since we know the odd number is nothing but an even number + 1. So ‘N’ can be expressed as 2*C + 1, where C is an integer.
Now N^2 will be (2*C + 1)^2 = 4*C^2 + 4*C + 1.
The steps are as follows:
- Let’s define a function square(X), which returns the square of any integer X.
- The base case is when N is 0 so we need to return 0.
- Now when ‘N’ is even, return 4*square(N / 2) i.e (square(N >> 1) << 2) (using bitwise shift operator).
- Else if the given number ‘N’ is odd return 4*square(floor(N / 2)) + 4*floor(N / 2) + 1 i.e. ((square(N >> 1) << 2) + ((N >> 1) << 2) + 1).
In the code implementation, we’ll use the right shift operator (>>) to calculate the floor(N / 2).
An edge case is when the integer is negative. We also know that the square of ‘N’ and ‘-N’ is the same, so whenever we are given a negative integer, we will convert it to a positive integer.
Our main approach here is to use the Russian Peasant Method. It is basically used to avoid the use of a multiplication operator.
The idea is to break down the given integer in powers of two and then use the bitwise shift operators to perform the multiplication with powers of 2.
For example:
7 can be broken down into powers of 2 as 1 + 2 + 4.
7*7 can be written as 7*(1 + 2 + 4), thus to perform the multiplication we can simply use the bitwise shift operator.
The steps are as follows :
- Firstly initialize the result as 0. Also, initialize two integers to ‘N’
- The idea is to keep on doubling the first number and reducing the second number to its half repeatedly till the second number doesn’t become 1.
- And whenever the second number becomes odd, we add the first number to the result because whenever the second number becomes odd it means that the first bit of the second number is set to 1 and hence we need to multiply the first number by (2 ^ 0) = 1 and add it to the result.
- Finally, return the result.