Generate an N-digit number made up of 1 or 2 only which is divisible by 2

0 0 6 minutes read

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 2^N.

Examples:

Input: N = 4
Output: 2112
Explanation: Since 2112 is divisible by 2⁴ ( = 16).

Input: N = 15
Output: 211111212122112

Approach: Follow the steps below to solve the problem:

Iterate over all values in the range [1, 2^N].
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 S_i == ‘0’, set S_i = ‘2’.
Convert the obtained string to an integer, say res using stoll().
If res is divisible by 2^N, 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

Output:

211111212122112

Time Complexity: O(2^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 zambiatek!