Calculate square of a number without using *, / and pow()
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 code int 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 Code for 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 times for ( $i = 1; $i < $n ; $i ++) $res += $n ; return $res ; } // Driver Code for ( $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> |
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 Code int 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 operators 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 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 # operators def 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 Code for 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 // operators using 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 operators function 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 operators function 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> |
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 code int 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 code public 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 calls for 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> |
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.
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 code int 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 Verma public 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 code for 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 calls for (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 |
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)
Contact Us