Given an integer N, the task is to generate an N-digit number which is comprising only of digits 1 or 2 and is divisible by 2N.
Examples:
Input: N = 4
Output: 2112
Explanation: Since 2112 is divisible by 24 ( = 16).Input: N = 15
Output: 211111212122112
Approach: Follow the steps below to solve the problem:
- Iterate over all values in the range [1, 2N].
- For each integer i in that range, generate its binary representation using bitset and store it in a string, say S.
- Reduce the length of the string S to N.
- Traverse the bits of S and if Si == ‘0’, set Si = ‘2’.
- Convert the obtained string to an integer, say res using stoll().
- If res is divisible by 2N, print the integer and break.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Utility function to find x^y in O(log(y)) long long int power( long long int x, unsigned long long int y) { // Stores the result long long int res = 1; // Update x if it is >= p while (y > 0) { // If y is odd if (y & 1) // Multiply x with res res = (res * x); // y must be even now // Set y = y/2 y = y >> 1; x = (x * x); } return res; } // Function to generate the N digit number // satisfying the given conditions void printNth( int N) { // Find all possible integers upto 2^N for ( long long int i = 1; i <= power(2, N); i++) { // Generate binary representation of i string s = bitset<64>(i).to_string(); // Reduce the length of the string to N string s1 = s.substr( s.length() - N, s.length()); for ( long long int j = 0; s1[j]; j++) { // If current bit is '0' if (s1[j] == '0' ) { s1[j] = '2' ; } } // Convert string to equivalent integer long long int res = stoll(s1, nullptr, 10); // If condition satisfies if (res % power(2, N) == 0) { // Print and break cout << res << endl; break ; } } } // Driver Code int main() { int N = 15; printNth(N); } |
Java
// Java program for the above approach import java.lang.*; import java.util.*; class GFG { // Utility function to find x^y in O(log(y)) static long power( long x, long y) { // Stores the result long res = 1 ; // Update x if it is >= p while (y > 0 ) { // If y is odd if ((y & 1 ) == 1 ) // Multiply x with res res = (res * x); // y must be even now // Set y = y/2 y = y >> 1 ; x = (x * x); } return res; } // Function to generate the N digit number // satisfying the given conditions static void printNth( int N) { // Find all possible integers upto 2^N for ( long i = 1 ; i <= power( 2 , N); i++) { // Generate binary representation of i String s = Long.toBinaryString(i); s = String.format( "%" + 64 + "s" , s) .replace( ' ' , '0' ); // Reduce the length of the string to N char [] s1 = s.substring(s.length() - N, s.length()) .toCharArray(); for ( int j = 0 ; j < s1.length; j++) { // If current bit is '0' if (s1[j] == '0' ) { s1[j] = '2' ; } } // Convert string to equivalent integer long res = Long.parseLong( new String(s1)); // If condition satisfies if (res % power( 2 , N) == 0 ) { // Print and break System.out.println(res); break ; } } } // Driver Code public static void main(String[] args) { int N = 15 ; printNth(N); } } // This code is contributed by phasing17 |
Python3
# Python program for the above approach # Utility function to find x^y in O(log(y)) def power(x, y): # Stores the result res = 1 # Update x if it is >= p while (y > 0 ): # If y is odd if (y & 1 ): # Multiply x with res res = (res * x) # y must be even now # Set y = y/2 y = y >> 1 x = (x * x) return res # Function to generate the N digit number # satisfying the given conditions def printNth(N): # Find all possible integers upto 2^N for i in range ( 1 ,power( 2 , N) + 1 ): # Generate binary representation of i s = "{:064b}" . format (i) # Reduce the length of the string to N s1 = s[ len (s) - N: 2 * len (s) - N] j = 0 while (j < len (s1)): # If current bit is '0' if (s1[j] = = '0' ): s1 = s1[:j] + '2' + s1[j + 1 :] j + = 1 # Convert string to equivalent integer res = int (s1) # If condition satisfies if (res % power( 2 , N) = = 0 ): # Prand break print (res) break # Driver Code N = 15 printNth(N) # This code is contributed by shubhamsingh10 |
C#
// C# program for the above approach using System; class GFG { // Utility function to find x^y in O(log(y)) static long power( long x, long y) { // Stores the result long res = 1; // Update x if it is >= p while (y > 0) { // If y is odd if ((y & 1) == 1) // Multiply x with res res = (res * x); // y must be even now // Set y = y/2 y = y >> 1; x = (x * x); } return res; } // Function to generate the N digit number // satisfying the given conditions static void printNth( int N) { // Find all possible integers upto 2^N for ( long i = 1; i <= power(2, N); i++) { // Generate binary representation of i string s = Convert.ToString(i, 2); s = s.PadLeft(64, '0' ); // Reduce the length of the string to N char [] s1 = s.Substring( s.Length - N).ToCharArray(); for ( int j = 0; j < s1.Length; j++) { // If current bit is '0' if (s1[j] == '0' ) { s1[j] = '2' ; } } // Convert string to equivalent integer long res = Convert.ToInt64( new string (s1), 10); // If condition satisfies if (res % power(2, N) == 0) { // Print and break Console.WriteLine(res); break ; } } } // Driver Code public static void Main( string [] args) { int N = 15; printNth(N); } } // This code is contributed by phasing17 |
Javascript
// JavaScript program for the above approach // Utility function to find x^y in O(log(y)) function power(x, y) { // Stores the result let res = 1; // Update x if it is >= p while (y > 0) { // If y is odd if (y & 1 != 0) // Multiply x with res res = (res * x); // y must be even now // Set y = y/2 y = y >> 1; x *= x; } return res; } // Function to generate the N digit number // satisfying the given conditions function printNth(N) { // Find all possible integers upto 2^N for ( var i = 1; i <= power(2, N); i++) { // Generate binary representation of i let s = i.toString(2).padStart(64, '0' ); // Reduce the length of the string to N let s1 = s.substring(s.length - N, 2 * s.length - N); s1 = s1.split( "" ); //console.log(s1); //console.log(s1); for ( var j = 0; s1[j]; j++) { // If current bit is '0' if (s1[j] == '0' ) { s1[j] = '2' ; } } // Convert string to equivalent integer let res = parseInt(s1.join( "" ), 10); // If condition satisfies if (res % power(2, N) == 0) { // Print and break console.log(res); break ; } } } // Driver Code let N = 15; printNth(N); // This code is contributed by phasing17 |
211111212122112
Time Complexity: O(2N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!