Given a positive integer N, the task is to find the value of (22 * X), where X is the binary representation of N. Since the answer can be very large, print it modulo 109 + 7.
Examples:
Input: N = 2
Output: 1048576
Explanation:
The binary representation of 2 is (10)2.
Therefore, the value of (22 * 10) % (109 + 7) = (220) % (109 + 7) = 1048576Input: N = 150
Output: 654430484
Naive Approach: The simplest approach to solve this problem is to generate the binary representation of N, say X, and calculate the value of (22 * X) % (109 + 7) using modular exponentiation:
Below is the implementation of the above approach:
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 Codeint 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 approachM = 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 Codeif __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 XX = X % M;// Base Caseif (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 nvar X = 0;// Stores power of 10var pow_10 = 1;// Calculate the binary// representation of nwhile (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 XX = (X * 2) % M;// Stores the value of// (2^(2 * x)) % (10^9 + 7) var res = power(2, X); return res; } // Driver codevar n = 2;document.write(findValue(n));// This code is contributed by 29AjayKumar </script> |
Output:
1048576
Time Complexity: O(log2(X)), where X is the binary representation of N
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized using Dynamic programming based on the following observations:
If N == 1 then the required output is (21)2 = (21)2
If N == 2 then the required output is (210)2 = (210)2
If N == 3 then the required output is (211)2 = (210 * 21)2
If N == 4 then the required output is (2100)2 = (2100)2
If N == 5 then the required output is (2101)2 = (2100 * 21)2
………………………..
Below is the relation between the dynamic programming states:
If N is a power of 2, then dp[N] = power(dp[N / 2], 10)
Otherwise, dp[N] = dp[(N & (-N))] * dp[N – (N & (-N))]
dp[N]2: Stores the required output for the positive integer N.
Follow the steps below to solve the problem:
- Initialize an array, say dp[], such that dp[i]2 stores the value of (22 * X) % (109 + 7), where X is the binary representation of i.
- Iterate over the range [3, N] using variable i and find all possible value of dp[i] using the tabulation method.
- Finally, print the value of dp[N]2
Below is the implementation of the above approach:
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 Codeint main(){ long long n = 150; cout << findValue(n); return 0;} |
Java
// Java program to implement// the above approachclass 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 approachM = 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 Codeif __name__ == '__main__': n = 150; print(findValue(n));# This code is contributed by 29AjayKumar |
C#
// C# program to implement// the above approachusing 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 approachvar 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 Codevar n = 150console.log(Number(findValue(n)))// This code is contributed by subhamgoyal2014.</script> |
Output:
654430484
Time Complexity: O(N *log(N))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!