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) = 1048576Entrada : 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