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