Calcular el valor de 2 elevado a la potencia del doble de la representación binaria de N

Dado un entero positivo N , la tarea es encontrar el valor de (2 2 * X ) , donde X es la representación binaria de N . Como la respuesta puede ser muy grande, imprímela módulo 10 9 + 7
Ejemplos:

Entrada: N = 2 
Salida: 1048576 
Explicación: 
La representación binaria de 2 es (10) 2
Por lo tanto, el valor de (2 2 * 10 ) % (10 9 + 7) = (2 20 ) % (10 9 + 7) = 1048576

Entrada : N = 150 
Salida: 654430484 
 

Enfoque ingenuo: el enfoque más simple para resolver este problema es generar la representación binaria de N , digamos X , y calcular el valor de (2 2 * X ) % (10 9 + 7) usando exponenciación modular :

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
#define M 1000000007
 
// Function to find the value
// of power(X, Y) in O(log Y)
long long power(long long X,
                long long Y)
{
    // Stores power(X, Y)
    long long res = 1;
 
    // Update X
    X = X % M;
 
    // Base Case
    if (X == 0)
        return 0;
 
    // Calculate power(X, Y)
    while (Y > 0) {
 
        // If Y is an odd number
        if (Y & 1) {
 
            // Update res
            res = (res * X) % M;
        }
 
        // Update Y
        Y = Y >> 1;
 
        // Update X
        X = (X * X) % M;
    }
 
    return res;
}
 
// Function to calculate
// (2^(2 * x)) % (10^9 + 7)
int findValue(long long int n)
{
 
    // Stores binary
    // representation of n
    long long X = 0;
 
    // Stores power of 10
    long long pow_10 = 1;
 
    // Calculate the binary
    // representation of n
    while (n) {
 
        // If n is an odd number
        if (n & 1) {
 
            // Update X
            X += pow_10;
        }
 
        // Update pow_10
        pow_10 *= 10;
 
        // Update n
        n /= 2;
    }
 
    // Double the value of X
    X = (X * 2) % M;
 
    // Stores the value of
    // (2^(2 * x)) % (10^9 + 7)
    long long res = power(2, X);
 
    return res;
}
 
// Driver Code
int main()
{
 
    long long n = 2;
    cout << findValue(n);
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.*;
class GFG
{
 
  static int M  = 1000000007;
 
  // Function to find the value
  // of power(X, Y) in O(log Y)
  static int  power(int  X,
                    int  Y)
  {
 
    // Stores power(X, Y)
    int  res = 1;
 
    // Update X
    X = X % M;
 
    // Base Case
    if (X == 0)
      return 0;
 
    // Calculate power(X, Y)
    while (Y > 0)
    {
 
      // If Y is an odd number
      if ((Y & 1) != 0)
      {
 
        // Update res
        res = (res * X) % M;
      }
 
      // Update Y
      Y = Y >> 1;
 
      // Update X
      X = (X * X) % M;
    }
    return res;
  }
  
  // Function to calculate
  // (2^(2 * x)) % (10^9 + 7)
  static int findValue(int n)
  {
 
    // Stores binary
    // representation of n
    int  X = 0;
 
    // Stores power of 10
    int  pow_10 = 1;
 
    // Calculate the binary
    // representation of n
    while (n != 0)
    {
 
      // If n is an odd number
      if ((n & 1) != 0)
      {
 
        // Update X
        X += pow_10;
      }
 
      // Update pow_10
      pow_10 *= 10;
 
      // Update n
      n /= 2;
    }
 
    // Double the value of X
    X = (X * 2) % M;
 
    // Stores the value of
    // (2^(2 * x)) % (10^9 + 7)
    int  res = power(2, X);
    return res;
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int  n = 2;
    System.out.println(findValue(n));
  }
}
 
// This code is contributed by susmitakundugoaldanga.

Python3

# Python3 program to implement
# the above approach
M = 1000000007
 
# Function to find the value
# of power(X, Y) in O(log Y)
def power(X, Y):
     
    # Stores power(X, Y)
    res = 1
 
    # Update X
    X = X % M
 
    # Base Case
    if (X == 0):
        return 0
 
    # Calculate power(X, Y)
    while (Y > 0):
 
        # If Y is an odd number
        if (Y & 1):
 
            # Update res
            res = (res * X) % M
 
        # Update Y
        Y = Y >> 1
 
        # Update X
        X = (X * X) % M
 
    return res
 
# Function to calculate
# (2^(2 * x)) % (10^9 + 7)
def findValue(n):
 
    # Stores binary
    # representation of n
    X = 0
 
    # Stores power of 10
    pow_10 = 1
 
    # Calculate the binary
    # representation of n
    while(n):
 
        # If n is an odd number
        if (n & 1):
             
            # Update X
            X += pow_10
 
        # Update pow_10
        pow_10 *= 10
 
        # Update n
        n //= 2
 
    # Double the value of X
    X = (X * 2) % M
 
    # Stores the value of
    # (2^(2 * x)) % (10^9 + 7)
    res = power(2, X)
 
    return res
 
# Driver Code
if __name__ == "__main__":
 
    n = 2
     
    print(findValue(n))
     
# This code is contributed by AnkThon

C#

// C# program to implement
// the above approach
using System;
class GFG
{
 
  static int M  = 1000000007;
 
  // Function to find the value
  // of power(X, Y) in O(log Y)
  static int  power(int  X,
                    int  Y)
  {
 
    // Stores power(X, Y)
    int  res = 1;
 
    // Update X
    X = X % M;
 
    // Base Case
    if (X == 0)
      return 0;
 
    // Calculate power(X, Y)
    while (Y > 0)
    {
 
      // If Y is an odd number
      if ((Y & 1) != 0)
      {
 
        // Update res
        res = (res * X) % M;
      }
 
      // Update Y
      Y = Y >> 1;
 
      // Update X
      X = (X * X) % M;
    }
    return res;
  }
  
  // Function to calculate
  // (2^(2 * x)) % (10^9 + 7)
  static int findValue(int n)
  {
 
    // Stores binary
    // representation of n
    int  X = 0;
 
    // Stores power of 10
    int  pow_10 = 1;
 
    // Calculate the binary
    // representation of n
    while (n != 0)
    {
 
      // If n is an odd number
      if ((n & 1) != 0)
      {
 
        // Update X
        X += pow_10;
      }
 
      // Update pow_10
      pow_10 *= 10;
 
      // Update n
      n /= 2;
    }
 
    // Double the value of X
    X = (X * 2) % M;
 
    // Stores the value of
    // (2^(2 * x)) % (10^9 + 7)
    int  res = power(2, X);
    return res;
  }
 
  // Driver code
  public static void Main(String[] args)
  {
    int  n = 2;
    Console.WriteLine(findValue(n));
  }
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
 
// javascript program to implement
// the above approach
  M  = 1000000007;
 
  // Function to find the value
  // of power(X, Y) in O(log Y)
function  power( X,Y)
{
 
    // Stores power(X, Y)
var  res = 1;
 
// Update X
X = X % M;
 
// Base Case
if (X == 0)
  return 0;
 
// Calculate power(X, Y)
while (Y > 0)
{
 
  // If Y is an odd number
  if ((Y & 1) != 0)
  {
 
    // Update res
    res = (res * X) % M;
  }
 
  // Update Y
  Y = Y >> 1;
 
  // Update X
      X = (X * X) % M;
    }
    return res;
  }
  
  // Function to calculate
  // (2^(2 * x)) % (10^9 + 7)
  function findValue(n)
  {
 
    // Stores binary
// representation of n
var  X = 0;
 
// Stores power of 10
var  pow_10 = 1;
 
// Calculate the binary
// representation of n
while (n != 0)
{
 
  // If n is an odd number
  if ((n & 1) != 0)
  {
 
    // Update X
    X += pow_10;
  }
 
  // Update pow_10
  pow_10 *= 10;
 
  // Update n
  n /= 2;
}
 
// Double the value of X
X = (X * 2) % M;
 
// Stores the value of
// (2^(2 * x)) % (10^9 + 7)
    var  res = power(2, X);
    return res;
  }
 
 // Driver code
 
var  n = 2;
document.write(findValue(n));
 
// This code is contributed by 29AjayKumar
 
</script>
Producción: 

1048576

 

Complejidad de tiempo: O(log 2 (X)), donde X es la representación binaria de N  
Espacio auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar utilizando la programación dinámica basada en las siguientes observaciones:

Si N == 1 entonces la salida requerida es (2 1 ) 2 = (2 1 ) 2 
Si N == 2 entonces la salida requerida es (2 10 ) 2 = (2 10 ) 2 
Si N == 3 entonces la salida requerida la salida es (2 11 ) 2 = (2 10 * 2 1 ) 2 
Si N == 4 entonces la salida requerida es (2 100 ) 2 = (2 100 ) 2 
Si N == 5 entonces la salida requerida es (2 101 ) 2 = (2 100 * 2 1 ) 2 
……………………….. 
A continuación se muestra la relación entre los estados de programación dinámica: 
Si N es una potencia de 2 , entonces dp[N] = potencia(dp[N / 2], 10) 
De lo contrario, dp[ N] = dp[(N & (-N))] * dp[N – (N & (-N))] 
dp[N] 2 : Almacena la salida requerida para el entero positivo N
 

Siga los pasos a continuación para resolver el problema: 

  • Inicialice una array, digamos dp[] , de modo que dp[i] 2 almacene el valor de (2 2 * X ) % (10 9 + 7) , donde X es la representación binaria de i .
  • Iterar sobre el rango [3, N] usando la variable i y encontrar todos los valores posibles de dp[i] usando el método de tabulación.
  • Finalmente, imprima el valor de dp[N] 2

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
#define M 1000000007
 
// Function to find the value
// of power(X, Y) in O(log Y)
long long power(long long X,
                long long Y)
{
    // Stores power(X, Y)
    long long res = 1;
 
    // Update X
    X = X % M;
 
    // Base Case
    if (X == 0)
        return 0;
 
    // Calculate power(X, Y)
    while (Y > 0) {
 
        // If Y is an odd number
        if (Y & 1) {
 
            // Update res
            res = (res * X) % M;
        }
 
        // Update Y
        Y = Y >> 1;
 
        // Update X
        X = (X * X) % M;
    }
 
    return res;
}
 
// Function to calculate
// (2^(2 * x)) % (10^9 + 7)
long long findValue(long long N)
{
 
    // dp[N] * dp[N]: Stores value
    // of (2^(2 * x)) % (10^9 + 7)
    long long dp[N + 1];
 
    // Base Case
    dp[1] = 2;
    dp[2] = 1024;
 
    // Iterate over the range [3, N]
    for (int i = 3; i <= N; i++) {
 
        // Stores rightmost
        // bit of i
        int y = (i & (-i));
 
        // Stores the value
        // of (i - y)
        int x = i - y;
 
        // If x is power
        // of 2
        if (x == 0) {
 
            // Update dp[i]
            dp[i]
                = power(dp[i / 2], 10);
        }
        else {
 
            // Update dp[i]
            dp[i]
                = (dp[x] * dp[y]) % M;
        }
    }
 
    return (dp[N] * dp[N]) % M;
}
 
// Driver Code
int main()
{
 
    long long n = 150;
    cout << findValue(n);
    return 0;
}

Java

// Java program to implement
// the above approach
class GFG
{
  static final long M = 1000000007;
 
  // Function to find the value
  // of power(X, Y) in O(log Y)
  static long power(long X,
                    long Y)
  {
 
    // Stores power(X, Y)
    long res = 1;
 
    // Update X
    X = X % M;
 
    // Base Case
    if (X == 0)
      return 0;
 
    // Calculate power(X, Y)
    while (Y > 0)
    {
 
      // If Y is an odd number
      if (Y % 2 == 1)
      {
 
        // Update res
        res = (res * X) % M;
      }
 
      // Update Y
      Y = Y >> 1;
 
      // Update X
      X = (X * X) % M;
    }
 
    return res;
  }
 
  // Function to calculate
  // (2^(2 * x)) % (10^9 + 7)
  static long findValue(int N)
  {
 
    // dp[N] * dp[N]: Stores value
    // of (2^(2 * x)) % (10^9 + 7)
    long []dp = new long[N + 1];
 
    // Base Case
    dp[1] = 2;
    dp[2] = 1024;
 
    // Iterate over the range [3, N]
    for (int i = 3; i <= N; i++)
    {
 
      // Stores rightmost
      // bit of i
      int y = (i & (-i));
 
      // Stores the value
      // of (i - y)
      int x = i - y;
 
      // If x is power
      // of 2
      if (x == 0)
      {
 
        // Update dp[i]
        dp[i]
          = power(dp[i / 2], 10);
      }
      else
      {
 
        // Update dp[i]
        dp[i]
          = (dp[x] * dp[y]) % M;
      }
    }
    return (dp[N] * dp[N]) % M;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int n = 150;
    System.out.print(findValue(n));
  }
}
 
// This code is contributed by shikhasingrajput

Python3

# Python3 program to implement
# the above approach
M = 1000000007;
 
# Function to find the value
# of power(X, Y) in O(log Y)
def power(X, Y):
     
    # Stores power(X, Y)
    res = 1;
 
    # Update X
    X = X % M;
 
    # Base Case
    if (X == 0):
        return 0;
 
    # Calculate power(X, Y)
    while (Y > 0):
 
        # If Y is an odd number
        if (Y % 2 == 1):
             
            # Update res
            res = (res * X) % M;
 
        # Update Y
        Y = Y >> 1;
 
        # Update X
        X = (X * X) % M;
    return res;
 
# Function to calculate
# (2^(2 * x)) % (10^9 + 7)
def findValue(N):
 
    # dp[N] * dp[N]: Stores value
    # of (2^(2 * x)) % (10^9 + 7)
    dp = [0]*(N + 1);
 
    # Base Case
    dp[1] = 2;
    dp[2] = 1024;
 
    # Iterate over the range [3, N]
    for i in range(3, N + 1):
 
        # Stores rightmost
        # bit of i
        y = (i & (-i));
 
        # Stores the value
        # of (i - y)
        x = i - y;
 
        # If x is power
        # of 2
        if (x == 0):
 
            # Update dp[i]
            dp[i] = power(dp[i // 2], 10);
        else:
 
            # Update dp[i]
            dp[i] = (dp[x] * dp[y]) % M;
 
    return (dp[N] * dp[N]) % M;
 
# Driver Code
if __name__ == '__main__':
    n = 150;
    print(findValue(n));
 
# This code is contributed by 29AjayKumar

C#

// C# program to implement
// the above approach
using System;
class GFG
{
  static readonly long M = 1000000007;
 
  // Function to find the value
  // of power(X, Y) in O(log Y)
  static long power(long X,
                    long Y)
  {
 
    // Stores power(X, Y)
    long res = 1;
 
    // Update X
    X = X % M;
 
    // Base Case
    if (X == 0)
      return 0;
 
    // Calculate power(X, Y)
    while (Y > 0)
    {
 
      // If Y is an odd number
      if (Y % 2 == 1)
      {
 
        // Update res
        res = (res * X) % M;
      }
 
      // Update Y
      Y = Y >> 1;
 
      // Update X
      X = (X * X) % M;
    }
 
    return res;
  }
 
  // Function to calculate
  // (2^(2 * x)) % (10^9 + 7)
  static long findValue(int N)
  {
 
    // dp[N] * dp[N]: Stores value
    // of (2^(2 * x)) % (10^9 + 7)
    long []dp = new long[N + 1];
 
    // Base Case
    dp[1] = 2;
    dp[2] = 1024;
 
    // Iterate over the range [3, N]
    for (int i = 3; i <= N; i++)
    {
 
      // Stores rightmost
      // bit of i
      int y = (i & (-i));
 
      // Stores the value
      // of (i - y)
      int x = i - y;
 
      // If x is power
      // of 2
      if (x == 0)
      {
 
        // Update dp[i]
        dp[i]
          = power(dp[i / 2], 10);
      }
      else
      {
 
        // Update dp[i]
        dp[i]
          = (dp[x] * dp[y]) % M;
      }
    }
    return (dp[N] * dp[N]) % M;
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    int n = 150;
    Console.Write(findValue(n));
  }
}
 
// This code contributed by shikhasingrajput

Javascript

<script>
 
// Javascript code to implement the approach
var M = 1000000007n
 
// Function to calculate
// (2^(2 * x)) % (10^9 + 7)
function findValue(N)
{
 
    // dp[N] * dp[N]: Stores value
    // of (2^(2 * x)) % (10^9 + 7)
    var dp = Array(N + 1)
 
    // Base Case
    dp[1] = 2n
    dp[2] = 1024n
 
    // Iterate over the range [3, N]
    for (let i = 3 ; i <= N ; i++) {
 
        // Stores rightmost
        // bit of i
        var y = (i & (-i));
 
        // Stores the value
        // of (i - y)
        var x = i - y;
 
        // If x is power
        // of 2
        if (x == 0) {
 
            dp[i] = 1n
            // Update dp[i]
            for(let j = 0 ; j < 10 ; j++){
                dp[i] = BigInt((BigInt(dp[i/2])*dp[i]) % M)
            }
        }
        else {
 
            // Update dp[i]
            dp[i] = (dp[x] * dp[y]) % M;
        }
    }
 
    return (dp[N] * dp[N]) % M;
}
 
 
// Driver Code
var n = 150
console.log(Number(findValue(n)))
 
// This code is contributed by subhamgoyal2014.
</script>
Producción: 

654430484

 

Complejidad de tiempo: O(N *log(N))  
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por mukulsomukesh 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 *