Genere un número de N dígitos formado por 1 o 2 solamente que sea divisible por 2N

Dado un número entero N , la tarea es generar un número de N dígitos que se componga solo de los dígitos 1 o 2 y sea divisible por 2 N .

Ejemplos:

Entrada: N = 4 
Salida: 2112 
Explicación: Dado que 2112 es divisible por 2 4 ( = 16).

Entrada: N = 15 
Salida: 211111212122112

Enfoque: siga los pasos a continuación para resolver el problema:

  • Iterar sobre todos los valores en el rango [1, 2 N ] .
  • Para cada entero i en ese rango, genere su representación binaria usando un conjunto de bits y guárdelo en una string , digamos S.
  • Reduzca la longitud de la string S a N .
  • Atraviese los bits de S y si S i == ‘0’ , establezca S i = ‘2’.
  • Convierta la string obtenida en un número entero, digamos res usando stoll() .
  • Si res es divisible por 2 N , imprima el entero y rompa .

A continuación se muestra la implementación del enfoque anterior:

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
Producción: 

211111212122112

 

Complejidad temporal: O(2 N )  
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por koulick_sadhu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *