Dado un entero x y un número positivo y, escribe una función que calcule x y bajo las siguientes condiciones.
a) La complejidad temporal de la función debe ser O(Log y)
b) El espacio adicional es O(1)
Ejemplos:
C++
// Iterative C program to implement pow(x, n)
#include <iostream>
using namespace std;
/* Iterative Function to calculate (x^y) in O(logy) */
int power(int x, unsigned int y)
{
int res = 1; // Initialize result
while (y > 0) {
// If y is odd, multiply x with result
if (y & 1)
res = res * x;
// y must be even now
y = y >> 1; // y = y/2
x = x * x; // Change x to x^2
}
return res;
}
// Driver program to test above functions
int main()
{
int x = 3;
unsigned int y = 5;
cout<<"Power is "<<power(x, y);
return 0;
}
// this code is contributed by shivanisinghss2110
C
// Iterative C++ program to implement pow(x, n)
#include <stdio.h>
/* Iterative Function to calculate (x^y) in O(logy) */
int power(int x, unsigned int y)
{
int res = 1; // Initialize result
while (y > 0) {
// If y is odd, multiply x with result
if (y & 1)
res = res * x;
// y must be even now
y = y >> 1; // y = y/2
x = x * x; // Change x to x^2
}
return res;
}
// Driver program to test above functions
int main()
{
int x = 3;
unsigned int y = 5;
printf("Power is %d", power(x, y));
return 0;
}
Java
// Iterative Java program
// to implement pow(x, n)
import java.io.*;
class GFG
{
/* Iterative Function to
calculate (x^y) in O(logy) */
static int power(int x, int y)
{
// Initialize result
int res = 1;
while (y > 0)
{
// If y is odd,
// multiply
// x with result
if ((y & 1) == 1)
res = res * x;
// y must be even now
y = y >> 1; // y = y/2
x = x * x; // Change x to x^2
}
return res;
}
// Driver Code
public static void main (String[] args)
{
int x = 3;
int y = 5;
System.out.println("Power is " +
power(x, y));
}
}
// This code is contributed
// by aj_36
Python3
# Iterative Python3 program
# to implement pow(x, n)
# Iterative Function to
# calculate (x^y) in O(logy)
def power(x, y):
# Initialize result
res = 1
while (y > 0):
# If y is odd, multiply
# x with result
if ((y & 1) == 1) :
res = res * x
# y must be even
# now y = y/2
y = y >> 1
# Change x to x^2
x = x * x
return res
# Driver Code
x = 3
y = 5
print("Power is ",
power(x, y))
# This code is contributed
# by ihritik
C#
// Iterative C# program
// to implement pow(x, n)
using System;
class GFG
{
/* Iterative Function to
calculate (x^y) in O(logy) */
static int power(int x, int y)
{
int res = 1; // Initialize result
while (y > 0)
{
// If y is odd, multiply
// x with result
if ((y & 1) == 1)
res = res * x;
// y must be even now
y = y >> 1; // y = y/2
x = x * x; // Change x to x^2
}
return res;
}
// Driver Code
static public void Main ()
{
int x = 3;
int y = 5;
Console.WriteLine("Power is "+
power(x, y));
}
}
// This code is contributed
// by aj_36
PHP
<?php
// Iterative php program
// to implement pow(x, n)>
// Iterative Function to
// calculate (x^y) in O(logy)
function power($x, $y)
{
// Initialize result
$res = 1;
while ($y > 0)
{
// If y is odd, multiply
// x with result
if ($y & 1)
$res = $res * $x;
// y must be even now
// y = y/2
$y = $y >> 1;
// Change x to x^2
$x = $x * $x;
}
return $res;
}
// Driver Code
$x = 3;
$y = 5;
echo "Power is ", power($x, $y);
// This code is contributed by ajit
?>
Javascript
<script>
// Iterative Javascript program to implement pow(x, n)
/* Iterative Function to calculate (x^y) in O(logy) */
function power(x, y)
{
// Initialize result
let res = 1;
while (y > 0) {
// If y is odd, multiply x with result
if (y & 1)
res = res * x;
// y must be even now
y = y >> 1; // y = y/2
x = x * x; // Change x to x^2
}
return res;
}
// Driver program to test above functions
let x = 3;
y = 5;
document.write("Power is " + power(x, y));
// This code is contributed by Mayank Tyagi
</script>
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