Dado un entero n, calcula el cuadrado de un número sin usar *, / y pow().
Ejemplos:
Input: n = 5 Output: 25 Input: 7 Output: 49 Input: n = 12 Output: 144
Una solución simple es agregar n repetidamente al resultado.
A continuación se muestra la implementación de esta 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>
Producción
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
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Enfoque 2:
Podemos hacerlo en tiempo O(Logn) usando operadores bit a bit . La idea se basa en el siguiente hecho.
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
¿Como funciona esto?
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) se puede calcular utilizando un operador de desplazamiento a la derecha bit a bit. Se pueden calcular 2*x y 4*x
A continuación se muestra la implementación basada en la idea anterior.
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>
Producción
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
Complejidad de tiempo: O (logn)
Espacio Auxiliar: O(1)
Enfoque 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.
A continuación se muestra la implementación basada en la idea anterior.
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>
Producción
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
Complejidad de tiempo: O (logn)
Espacio Auxiliar: O(1)
Gracias a Sanjay por la solución del enfoque 3.
Este artículo es una contribución de Ujjwal Jain . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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
Producción
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
Complejidad de tiempo: O (logn)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA