Given an integer n, calculate the square of a number without using *, / and pow().
Examples :
Input: n = 5 Output: 25 Input: 7 Output: 49 Input: n = 12 Output: 144
A Simple Solution is to repeatedly add n to result.
Below is the implementation of this idea.
C++
// Simple solution to calculate square without// using * and pow()#include <iostream>using namespace std;int square(int n){ // handle negative input if (n < 0) n = -n; // Initialize result int res = n; // Add n to res n-1 times for (int i = 1; i < n; i++) res += n; return res;}// Driver codeint main(){ for (int n = 1; n <= 5; n++) cout << "n = " << n << ", n^2 = " << square(n) << endl; return 0;} |
Java
// Java Simple solution to calculate// square without using * and pow()import java.io.*;class GFG { public static int square(int n) { // handle negative input if (n < 0) n = -n; // Initialize result int res = n; // Add n to res n-1 times for (int i = 1; i < n; i++) res += n; return res; } // Driver code public static void main(String[] args) { for (int n = 1; n <= 5; n++) System.out.println("n = " + n + ", n^2 = " + square(n)); }}// This code is contributed by sunnysingh |
Python3
# Simple solution to# calculate square without# using * and pow()def square(n): # handle negative input if (n < 0): n = -n # Initialize result res = n # Add n to res n-1 times for i in range(1, n): res += n return res# Driver Codefor n in range(1, 6): print("n =", n, end=", ") print("n^2 =", square(n))# This code is contributed by# Smitha Dinesh Semwal |
C#
// C# Simple solution to calculate// square without using * and pow()using System;class GFG { public static int square(int n) { // handle negative input if (n < 0) n = -n; // Initialize result int res = n; // Add n to res n-1 times for (int i = 1; i < n; i++) res += n; return res; } // Driver code public static void Main() { for (int n = 1; n <= 5; n++) Console.WriteLine("n = " + n + ", n^2 = " + square(n)); }}// This code is contributed by Sam007 |
PHP
<?php// PHP implementation to// calculate square// without using * and pow()function square($n){// handle negative input if ($n < 0) $n = -$n;// Initialize result $res = $n;// Add n to res n-1 timesfor ($i = 1; $i < $n; $i++) $res += $n;return $res;}// Driver Codefor ($n = 1; $n<=5; $n++) echo "n = ", $n, ", ", "n^2 = ", square($n), "\n "; // This code is contributed by Ajit?> |
Javascript
<script>// Simple solution to calculate square without// using * and pow()function square(n){ // handle negative input if (n < 0) n = -n; // Initialize result let res = n; // Add n to res n-1 times for (let i = 1; i < n; i++) res += n; return res;}// Driver code for (let n = 1; n <= 5; n++) document.write("n= " + n +", n^2 = " + square(n) + "<br>"); //This code is contributed by Mayank Tyagi</script> |
Output
n = 1, n^2 = 1 n = 2, n^2 = 4 n = 3, n^2 = 9 n = 4, n^2 = 16 n = 5, n^2 = 25
Time Complexity: O(n)
Auxiliary Space: O(1)
Approach 2:
We can do it in O(Logn) time using bitwise operators. The idea is based on the following fact.
square(n) = 0 if n == 0
if n is even
square(n) = 4*square(n/2)
if n is odd
square(n) = 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
How does this work?
If n is even, it can be written as n = 2*x n2 = (2*x)2 = 4*x2 If n is odd, it can be written as n = 2*x + 1 n2 = (2*x + 1)2 = 4*x2 + 4*x + 1
floor(n/2) can be calculated using a bitwise right shift operator. 2*x and 4*x can be calculated
Below is the implementation based on the above idea.
C++
// Square of a number using bitwise operators#include <bits/stdc++.h>using namespace std;int square(int n){ // Base case if (n == 0) return 0; // Handle negative number if (n < 0) n = -n; // Get floor(n/2) using right shift int x = n >> 1; // If n is odd if (n & 1) return ((square(x) << 2) + (x << 2) + 1); else // If n is even return (square(x) << 2);}// Driver Codeint main(){ // Function calls for (int n = 1; n <= 5; n++) cout << "n = " << n << ", n^2 = " << square(n) << endl; return 0;} |
Java
// Square of a number using// bitwise operatorsclass GFG { static int square(int n) { // Base case if (n == 0) return 0; // Handle negative number if (n < 0) n = -n; // Get floor(n/2) using // right shift int 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); } // Driver code public static void main(String args[]) { // Function calls for (int n = 1; n <= 5; n++) System.out.println("n = " + n + " n^2 = " + square(n)); }}// This code is contributed by Sam007 |
Python3
# Square of a number using bitwise# operatorsdef square(n): # Base case if (n == 0): return 0 # Handle negative number if (n < 0): n = -n # Get floor(n/2) using # right shift x = n >> 1 # If n is odd if (n & 1): return ((square(x) << 2) + (x << 2) + 1) # If n is even else: return (square(x) << 2)# Driver Codefor n in range(1, 6): print("n = ", n, " n^2 = ", square(n))# This code is contributed by Sam007 |
C#
// Square of a number using bitwise// operatorsusing System;class GFG { static int square(int n) { // Base case if (n == 0) return 0; // Handle negative number if (n < 0) n = -n; // Get floor(n/2) using // right shift int 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); } // Driver code static void Main() { for (int n = 1; n <= 5; n++) Console.WriteLine("n = " + n + " n^2 = " + square(n)); }}// This code is contributed by Sam0007. |
PHP
<?php// Square of a number using// bitwise operatorsfunction square($n){ // Base case if ($n==0) return 0; // Handle negative number if ($n < 0) $n = -$n; // Get floor(n/2) // using right shift $x = $n >> 1; // If n is odd if ($n & 1) return ((square($x) << 2) + ($x << 2) + 1); else // If n is even return (square($x) << 2);} // Driver Code for ($n = 1; $n <= 5; $n++) echo "n = ", $n, ", n^2 = ", square($n),"\n"; // This code is contributed by ajit?> |
Javascript
<script>// Square of a number using bitwise operatorsfunction 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 & 1) return ((square(x) << 2) + (x << 2) + 1); else // If n is even return (square(x) << 2);}// Driver Code // Function calls for (let n = 1; n <= 5; n++) document.write("n = " + n + ", n^2 = " + square(n) +"<br>"); //This code is contributed by Mayank Tyagi</script> |
Output
n = 1, n^2 = 1 n = 2, n^2 = 4 n = 3, n^2 = 9 n = 4, n^2 = 16 n = 5, n^2 = 25
Time Complexity: O(log n)
Auxiliary Space: O(log n) as well, as the number of function calls stored in the call stack will be logarithmic to the size of the input
Approach 3:
For a given number `num` we get square of it by multiplying number as `num * num`.
Now write one of `num` in square `num * num` in terms of power of `2`. Check below examples.
Eg: num = 10, square(num) = 10 * 10
= 10 * (8 + 2) = (10 * 8) + (10 * 2)
num = 15, square(num) = 15 * 15
= 15 * (8 + 4 + 2 + 1) = (15 * 8) + (15 * 4) + (15 * 2) + (15 * 1)
Multiplication with power of 2's can be done by left shift bitwise operator.
Below is the implementation based on the above idea.
C++
// Simple solution to calculate square without// using * and pow()#include <iostream>using namespace std;int square(int num){ // handle negative input if (num < 0) num = -num; // Initialize result int result = 0, times = num; while (times > 0) { int possibleShifts = 0, currTimes = 1; while ((currTimes << 1) <= times) { currTimes = currTimes << 1; ++possibleShifts; } result = result + (num << possibleShifts); times = times - currTimes; } return result;}// Driver codeint main(){ // Function calls for (int n = 10; n <= 15; ++n) cout << "n = " << n << ", n^2 = " << square(n) << endl; return 0;}// This code is contributed by sanjay235 |
Java
// Simple solution to calculate square// without using * and pow()import java.io.*;class GFG{ public static int square(int num){ // Handle negative input if (num < 0) num = -num; // Initialize result int result = 0, times = num; while (times > 0) { int possibleShifts = 0, currTimes = 1; while ((currTimes << 1) <= times) { currTimes = currTimes << 1; ++possibleShifts; } result = result + (num << possibleShifts); times = times - currTimes; } return result;}// Driver codepublic static void main(String[] args){ for(int n = 10; n <= 15; ++n) { System.out.println("n = " + n + ", n^2 = " + square(n)); }}}// This code is contributed by RohitOberoi |
Python3
# Simple solution to calculate square without# using * and pow()def square(num): # Handle negative input if (num < 0): num = -num # Initialize result result, times = 0, num while (times > 0): possibleShifts, currTimes = 0, 1 while ((currTimes << 1) <= times): currTimes = currTimes << 1 possibleShifts += 1 result = result + (num << possibleShifts) times = times - currTimes return result# Driver Code# Function callsfor n in range(10, 16): print("n =", n, ", n^2 =", square(n))# This code is contributed by divyesh072019 |
C#
// Simple solution to calculate square// without using * and pow()using System;class GFG { static int square(int num) { // Handle negative input if (num < 0) num = -num; // Initialize result int result = 0, times = num; while (times > 0) { int possibleShifts = 0, currTimes = 1; while ((currTimes << 1) <= times) { currTimes = currTimes << 1; ++possibleShifts; } result = result + (num << possibleShifts); times = times - currTimes; } return result; } static void Main() { for(int n = 10; n <= 15; ++n) { Console.WriteLine("n = " + n + ", n^2 = " + square(n)); } }}// This code is contributed by divyeshrabadiy07 |
Javascript
<script>// Simple solution to calculate square without// using * and pow()function square(num){ // handle negative input if (num < 0) num = -num; // Initialize result let result = 0, times = num; while (times > 0) { let possibleShifts = 0, currTimes = 1; while ((currTimes << 1) <= times) { currTimes = currTimes << 1; ++possibleShifts; } result = result + (num << possibleShifts); times = times - currTimes; } return result;}// Driver code // Function calls for (let n = 10; n <= 15; ++n) document.write("n = " + n + ", n^2 = " + square(n) + "<br>");//This code is contributed by Mayank Tyagi</script> |
Output
n = 10, n^2 = 100 n = 11, n^2 = 121 n = 12, n^2 = 144 n = 13, n^2 = 169 n = 14, n^2 = 196 n = 15, n^2 = 225
Time Complexity: O(logn)
Auxiliary Space: O(1)
Thanks to Sanjay for approach 3 solution.
This article is contributed by Ujjwal Jain. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
C++
// Simple solution to calculate square without// using * and pow()#include <iostream>using namespace std;int square(int num){ // handle negative input if (num < 0) num = -num; // Initialize power of 2 and result int power = 0, result = 0; int temp = num; while (temp) { if (temp & 1) { // result=result+(num*(2^power)) result += (num << power); } power++; // temp=temp/2 temp = temp >> 1; } return result;}// Driver codeint main(){ // Function calls for (int n = 10; n <= 15; ++n) cout << "n = " << n << ", n^2 = " << square(n) << endl; return 0;}// This code is contributed by Aditya Verma |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.*;// java program for Simple solution to calculate square without// using * and pow()// This code is contributed by Aditya Vermapublic class Main { public static int square(int num) { // handle negative input if (num < 0) num = -num; // Initialize power of 2 and result int power = 0, result = 0; int temp = num; while (temp > 0) { if ((temp & 1) > 0) { // result=result+(num*(2^power)) result += (num << power); } power++; // temp=temp/2 temp = temp >> 1; } return result; } public static void main(String[] args) { // Function calls for (int n = 10; n <= 15; ++n) System.out.println("n = " + n + ", n^2 = " + square(n)); }}// The code is contributed by Nidhi goel. |
Python3
def square(num): # handle negative input if num < 0: num = -num # Initialize power of 2 and result power, result = 0, 0 temp = num while temp: if temp & 1: # result=result+(num*(2^power)) result += (num << power) power += 1 # temp=temp/2 temp = temp >> 1 return result# Driver codefor n in range(10, 16): print(f"n = {n}, n^2 = {square(n)}") |
Javascript
// Simple solution to calculate square without// using * and pow()function square(num) { // handle negative input if (num < 0) num = -num; // Initialize power of 2 and result let power = 0, result = 0; let temp = num; while (temp) { if (temp & 1) { // result=result+(num*(2^power)) result += (num << power); } power++; // temp=temp/2 temp = temp >> 1; } return result;}// Driver code// Function callsfor (let n = 10; n <= 15; ++n) console.log(`n = ${n}, n^2 = ${square(n)}`);// This code is contributed by phasing17 |
C#
// Simple solution to calculate square without// using * and pow()using System;public class Program{ public static int Square(int num) { // handle negative input if (num < 0) num = -num; // Initialize power of 2 and result int power = 0, result = 0; int temp = num; while (temp > 0) { if ((temp & 1) > 0) { // result=result+(num*(2^power)) result += (num << power); } power++; // temp=temp/2 temp = temp >> 1; } return result; } public static void Main() { // Function calls for (int n = 10; n <= 15; ++n) Console.WriteLine("n = " + n + ", n^2 = " + Square(n)); }}// Contributed by adityasha4x71 |
Output
n = 10, n^2 = 100 n = 11, n^2 = 121 n = 12, n^2 = 144 n = 13, n^2 = 169 n = 14, n^2 = 196 n = 15, n^2 = 225
Time Complexity: O(logn)
Auxiliary Space: O(1)
