Competitive Programming: Calculate the square of a number without using *, / and pow()

  Hello everyone ... 

Here we are going to solve a Competitive Programming problem related to Bit Manipulation.

Problem Statement

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

Examples

Input: N = 4
Output: 16
Explanation:
4*4 = 16

Constraints

1 ≤ N ≤ 108

Expectations

Expected Time Complexity: O(logN)
Expected Space Complexity: O(1)

Solution

Approach 

C++ Code

	#include<bits/stdc++.h>
	using namespace std;
	int main() {
	int n;
	cin >> n;
	n = abs(n);
	int temp_n = n;
	int res = 0;
	int pos = 0;
	while(temp_n) {
	if(temp_n & 1) {
	res += (n<<pos);
	}
	pos++;
	temp_n >>= 1;
	}
	cout << res << endl;
	}

view raw calculate-square-without-div-mul-pow.cpp hosted with ❤ by GitHub

Time Complexity

Since we are only iterating through the bits of N in its binary representation, this solution's time complexity is O(LogN). 

Space Complexity

Since we are using constant space, this solution's space complexity is O(1).

Hooray! We successfully solved this problem with the expected time and space complexity.

Hopefully, you enjoyed this blog post and learned something new. If you want to share anything or if you have any doubts or suggestions please comment below. 

Thank you, guys. 

Have a nice day and stay tuned for new blog posts. Bye ...👋