Escriba una función O(Log y) iterativa para pow(x, y)

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *