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 conditionsvoid 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 Codeint main(){ int N = 15; printNth(N);} |
Java
// Java program for the above approachimport 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 conditionsdef 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 CodeN = 15printNth(N)# This code is contributed by shubhamsingh10 |
C#
// C# program for the above approachusing 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 conditionsfunction 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 Codelet N = 15;printNth(N);// This code is contributed by phasing17 |
Output:
211111212122112
Time Complexity: O(2N)
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!
