Dada una string S que consta de N dígitos, la tarea es imprimir todas las combinaciones posibles de los dígitos de S que es una potencia perfecta de 2 .
Ejemplos:
Entrada: S = “614”
Salida: 4
Explicación:
Todas las combinaciones posibles de dígitos de S que son potencia perfecta de 2 son 1, 4, 16, 64.Entrada: S = “6”
Salida: 0
Enfoque: El problema dado se puede resolver usando Backtracking . La idea es generar todas las permutaciones posibles de la string S si es una potencia perfecta de 2 y luego imprimirla. Siga los pasos a continuación para resolver el problema:
- Defina una función check(int number) para verificar si el número dado es una potencia de 2 y realice las siguientes tareas:
- Si el número es igual a 0, devuelve falso.
- Si el AND bit a bit del número y el número 1, devuelve verdadero, de lo contrario, devuelve falso.
- Defina una función de cálculo (int arr[], string ans) y realice las siguientes tareas:
- Si la longitud de la string ans no es igual a 0 y el valor de la función . check(Integer.parseInt(ans.trim())) devuelve verdadero, luego agregue este valor al HashSet H[] .
- Itere sobre un rango [0, 10] usando la variable i y realice las siguientes tareas:
- Inicialice un HashSet H[] para almacenar los posibles números de string que son una potencia de 2.
- Inicialice una array , digamos temp[] para almacenar las frecuencias de los enteros en la string str .
- Iterar en un ciclo while hasta que N no sea igual a 0 y realizar los siguientes pasos:
- Inicialice la variable rem como N%10 y aumente el valor de temp[rem] en 1 .
- Divide el valor de N por 10 .
- Llame a la función calcular (temp, «») para encontrar las posibles permutaciones de la string S.
- Después de realizar los pasos anteriores, imprima el HashSet como resultado.
A continuación se muestra la implementación del enfoque anterior.
C++
#include <bits/stdc++.h>
using namespace std;
// Stores the all possible generated
// integers from the given string
unordered_set<int> hs;
// Function to check if the
// number is power of 2
bool check(int number)
{
// If number is 0, then it
// can't be a power of 2
if (number == 0) {
return false;
}
// If the bitwise AND of n
// and n-1 is 0, then only
// it is a power of 2
if ((number & (number - 1)) == 0) {
return true;
}
return false;
}
// Function to generate the numbers
void calculate(int* arr, string ans)
{
if (ans.length() != 0) {
// Checking the number
if (check(stoi(ans))) {
hs.insert(stoi(ans));
}
}
// Iterate over the range
for (int i = 0; i < 10; ++i) {
if (arr[i] == 0) {
continue;
}
else {
// Use the number
arr[i]--;
calculate(arr,(ans + to_string(i)));
// Backtracking Step
arr[i]++;
}
}
}
// Function to find the all possible
// permutations
void generatePermutation(int n)
{
hs.clear();
// Stores the frequency of digits
int temp[10];
for (int i = 0; i < 10; i++) {
temp[i] = 0;
}
// Iterate over the number
while (n != 0) {
int rem = n % 10;
temp[rem]++;
n = n / 10;
}
// Function Call
calculate(temp, "");
// Print the result
cout << hs.size() << "\n";
for (auto i : hs) {
cout << i << " ";
}
}
int main()
{
int N = 614;
generatePermutation(N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
public class GFG {
// Stores the all possible generated
// integers from the given string
static HashSet<Integer> H = new HashSet<>();
// Function to check if the
// number is power of 2
static boolean check(int number)
{
// If number is 0, then it
// can't be a power of 2
if (number == 0) {
return false;
}
// If the bitwise AND of n
// and n-1 is 0, then only
// it is a power of 2
if ((number & (number - 1)) == 0) {
return true;
}
return false;
}
// Function to generate the numbers
static void calculate(
int arr[], String ans)
{
if (ans.length() != 0) {
// Checking the number
if (check(Integer.parseInt(
ans.trim()))) {
H.add(Integer.parseInt(
ans.trim()));
}
}
// Iterate over the range
for (int i = 0; i < arr.length; ++i) {
if (arr[i] == 0) {
continue;
}
else {
// Use the number
arr[i]--;
calculate(arr, ans + i);
// Backtracking Step
arr[i]++;
}
}
}
// Function to find the all possible
// permutations
static void generatePermutation(int n)
{
// Stores the frequency of digits
int temp[] = new int[10];
// Iterate over the number
while (n != 0) {
int rem = n % 10;
temp[rem]++;
n = n / 10;
}
// Function Call
calculate(temp, "");
// Print the result
System.out.println(H.size());
System.out.println(H);
}
// Driver Code
public static void main(String[] args)
{
int N = 614;
generatePermutation(N);
}
}
Python3
# Python3 program for the above approach # Stores the all possible generated # integers from the given string H = set() # Function to check if the # number is power of 2 def check(number): # If number is 0, then it # can't be a power of 2 if (number == 0): return False # If the bitwise AND of n # and n-1 is 0, then only # it is a power of 2 if ((number & (number - 1)) == 0): return True return False # Function to generate the numbers def calculate(arr, ans): if (len(ans) != 0): # Checking the number if (check(int(ans))): H.add(int(ans)) # Iterate over the range for i in range(len(arr)): if (arr[i] == 0): continue else: # Use the number arr[i]-=1 calculate(arr, ans + str(i)) # Backtracking Step arr[i]+=1 # Function to find the all possible # permutations def generatePermutation(n): # Stores the frequency of digits h = [16, 64, 1, 4] temp = [0]*(10) # Iterate over the number while (n != 0): rem = n % 10 temp[rem]+=1 n = int(n / 10) # Function Call calculate(temp, "") # Print the result print(len(H)) print(h) N = 614 generatePermutation(N) # This code is contributed by divyesh072019.
C#
using System;
using System.Collections.Generic;
public class GFG{
// Stores the all possible generated
// integers from the given string
static HashSet<int> H = new HashSet<int>();
// Function to check if the
// number is power of 2
static bool check(int number)
{
// If number is 0, then it
// can't be a power of 2
if (number == 0) {
return false;
}
// If the bitwise AND of n
// and n-1 is 0, then only
// it is a power of 2
if ((number & (number - 1)) == 0) {
return true;
}
return false;
}
// Function to generate the numbers
static void calculate(
int[] arr, String ans)
{
if (ans.Length != 0) {
// Checking the number
if (check(int.Parse(
ans))) {
H.Add(int.Parse(
ans));
}
}
// Iterate over the range
for (int i = 0; i < arr.Length; ++i) {
if (arr[i] == 0) {
continue;
}
else {
// Use the number
arr[i]--;
calculate(arr, ans + i);
// Backtracking Step
arr[i]++;
}
}
}
// Function to find the all possible
// permutations
static void generatePermutation(int n)
{
// Stores the frequency of digits
int[] temp = new int[10];
// Iterate over the number
while (n != 0) {
int rem = n % 10;
temp[rem]++;
n = n / 10;
}
// Function Call
calculate(temp, "");
// Print the result
Console.WriteLine(H.Count);
foreach(var val in H){
Console.Write(val+" ");
}
}
static public void Main (){
int N = 614;
generatePermutation(N);
}
}
// This code is contributed by maddler.
Javascript
<script>
// Javascript program for the above approach
// Stores the all possible generated
// integers from the given string
let H = new Set();
// Function to check if the
// number is power of 2
function check(number)
{
// If number is 0, then it
// can't be a power of 2
if (number == 0) {
return false;
}
// If the bitwise AND of n
// and n-1 is 0, then only
// it is a power of 2
if ((number & (number - 1)) == 0) {
return true;
}
return false;
}
// Function to generate the numbers
function calculate(arr, ans)
{
if (ans.length != 0) {
// Checking the number
if (check(parseInt(ans))) {
H.add(parseInt(ans));
}
}
// Iterate over the range
for (let i = 0; i < arr.length; ++i) {
if (arr[i] == 0) {
continue;
}
else {
// Use the number
arr[i]--;
calculate(arr, ans + i);
// Backtracking Step
arr[i]++;
}
}
}
// Function to find the all possible
// permutations
function generatePermutation(n)
{
// Stores the frequency of digits
let temp = new Array(10);
let h = [16, 64, 1, 4];
temp.fill(0);
// Iterate over the number
while (n != 0) {
let rem = n % 10;
temp[rem]++;
n = parseInt(n / 10, 10);
}
// Function Call
calculate(temp, "");
// Print the result
document.write(H.size + "</br>" + "[");
for(let i = 0; i < h.length - 1; i++)
{
document.write(h[i] + ", ");
}
document.write(h[h.length - 1] + "]");
}
let N = 614;
generatePermutation(N);
// This code is contributed by decode2207.
</script>
Producción:
4 [16, 64, 1, 4]
Complejidad temporal: O(N*9 N )
Espacio auxiliar: O(1)
Enfoque eficiente : la idea es generar todas las potencias de dos inicialmente y almacenarlas en una estructura de datos adecuada («conjunto DE CPP» en este caso) y comprobar si existe una potencia de dos en la string.
- La dificultad aquí es verificar si el poder de dos salidas en string.
- un enfoque ingenuo para verificar si la potencia de dos salidas en la string es generando todas las permutaciones posibles de strings y verificando si esa string es o tiene una potencia de 2, este enfoque no se recomienda ya que la complejidad del tiempo es alrededor de O (n!)
- Un enfoque eficiente es usar una array de conteo que almacene el conteo de dígitos decimales y verificar si el conteo de cada dígito decimal de una potencia de 2 es menor o igual al conteo de dígitos decimales presentes en la string.
C++14
#include<bits/stdc++.h>
using namespace std;
void calculatePower(string s,int n,set<long long>&ans)
{
// cnt_s is stores the count of each decimal digits of string s
int cnt_s[10]={0};
// Here we calculate the count of each decimal digit of string s
for(int i=0;i<n;i++)
{
cnt_s[s[i]-'0']++;
}
// our main logic is to generate powers of 2 and store the count of decimal digit of powers of 2 in
// cnt_a i.e we check for every i in range(0,10): if(cnt_s[i]>=cnt_[a])
long val=2,one=1;
long maxval=(one<<62);
// maxval has max power of 2 in range of long
// in this loop we generate powers of 2
while(val<=maxval&&val>0)
{
long temp=val;
int cnt_a[10]={0};
// cnt_a has count of decimal digits in kth power of 2
while(temp)
{
long remainder=(temp%10);
cnt_a[remainder]++;
temp/=10;
}
// checking if a power of 2 present in string s
bool fl=true;
for(int i=0;i<10;i++)
{
if(cnt_a[i]>cnt_s[i])
{
fl=false;
break;
}
}
// if the power of 2 present in s we add it to set
if(fl)
{
ans.insert(val);
}
val*=2;
}
}
int main()
{
string s="614";
int n=s.length();
// set-ans has all possible powers of 2 that are present in string
set<long long>ans;
calculatePower(s,n,ans);
cout<<"THE TOTAL POSSIBLE COMBINATIONS THAT ARE POWER OF 2 ARE: "<<ans.size()<<"\n";
for(auto i:ans)
{
cout<<i<<"\n";
}
}
C
#include<stdio.h>
#include<string.h>
void calculatePower(char s[],int n)
{
// cnt_s is stores the count of each decimal digits of string s
int cnt_s[10]={0};
// Here we calculate the count of each decimal digit of string s
for(int i=0;i<n;i++)
{
cnt_s[s[i]-'0']++;
}
// our main logic is to generate powers of 2 and store the count of decimal digit of powers of 2 in
// cnt_a i.e we check for every i in range(0,10): if(cnt_s[i]>=cnt_[a])
long val=2,one=1;
long maxval=(one<<62);
// maxval has max power of 2 in range of long
// in this loop we generate power of 2
while(val<=maxval&&val>0)
{
long temp=val;
int cnt_a[10]={0};
// cnt_a has count of decimal digits in kth power of 2
while(temp)
{
long remainder=(temp%10);
cnt_a[remainder]++;
temp/=10;
}
// checking if a power of 2 present in string s
int fl=1;
for(int i=0;i<10;i++)
{
if(cnt_a[i]>cnt_s[i])
{
fl=0;
break;
}
}
if(fl)
{
printf("%ld is present in string\n",val);
}
val*=2;
}
}
int main()
{
char s[]="614";
int n=strlen(s);
calculatePower(s,n);
}
Java
import java.util.*;
public class Main
{
public static void calculatePower(String s,int n)
{
ArrayList<Long> ans=new ArrayList<Long>();
// cnt_s is stores the count of each decimal digits of string s
int cnt_s[]=new int[10];
// Here we calculate the count of each decimal digit of string s
for(int i=0;i<n;i++)
{
cnt_s[s.charAt(i)-'0']++;
}
// our main logic is to generate powers of 2 and store the count of decimal digit of powers of 2 in
// cnt_a i.e we check for every i in range(0,10): if(cnt_s[i]>=cnt_[a])
long value=2,one=1;
long maxvalue=(one<<62);
// maxval has max power of 2 in range of long
// in this loop we generate powers of 2
while(value<=maxvalue && value>=0)
{
long temp=value;
int cnt_a[]=new int[10];
// cnt_a has count of decimal digits in kth power of 2
while(temp>0)
{
long remainder=(temp%10);
cnt_a[(int)remainder]++;
temp/=10;
}
// checking if a power of 2 present in string s
boolean fl=true;
for(int i=0;i<10;i++)
{
if(cnt_a[i]>cnt_s[i])
{
fl=false;
break;
}
}
// if the power of 2 present in s we add it to ans
if(fl)
{
ans.add(value);
}
value*=2;
}
System.out.println("THE TOTAL POSSIBLE COMBINATIONS THAT ARE POWER OF 2 ARE: "+ans.size());
for(Long i:ans)
{
System.out.println(i);
}
}
public static void main(String[] args) {
String s="614";
int n=s.length();
calculatePower(s,n);
}
}
Python3
def calculatePower(s,n):
# cnt_s is stores the count of each decimal digits of string s
cnt_s=[0]*10
# Here we calculate the count of each decimal digit of string s
for i in s:
cnt_s[int(i)]+=1
# our main logic is to generate powers of 2 and store the count of decimal digit of powers of 2 in cnt_a i.e we check for every i in range(0,10): if(cnt_s[i]>=cnt_[a])
one=1
value=2
maxvalue=(one<<62)
ans=[]
# maxval has max power of 2 in range of long in this loop we generate powers of 2
while(value<=maxvalue):
# cnt_a has count of decimal digits in kth power of 2
cnt_a=[0]*10
fl=True
temp=value
while(temp>0):
remainder=temp%10
cnt_a[remainder]+=1
temp=int(temp/10)
# checking if a power of 2 present in string s
for i in range(0,10):
if(cnt_a[i]>cnt_s[i]):
fl=False
break
# if the power of 2 present in s we add it to ans
if(fl):
ans.append(value)
value*=2
print("THE TOTAL POSSIBLE COMBINATIONS THAT ARE POWER OF 2 ARE: ",len(ans))
for i in ans:
print(i)
s="614"
n=len(s)
calculatePower(s,n)
C#
using System;
using System.Collections.Generic;
public class GFG {
public static void calculatePower(string s, int n)
{
List<long> ans = new List<long>();
// cnt_s is stores the count of each decimal digits
// of string s
int[] cnt_s = new int[10];
// Here we calculate the count of each decimal digit
// of string s
for (int i = 0; i < n; i++) {
cnt_s[s[i] - '0']++;
}
// our main logic is to generate powers of 2 and
// store the count of decimal digit of powers of 2
// in cnt_a i.e we check for every i in range(0,10):
// if(cnt_s[i]>=cnt_[a])
long value = 2, one = 1;
long maxvalue = (one << 62);
// maxval has max power of 2 in range of long
// in this loop we generate powers of 2
while (value <= maxvalue && value >= 0) {
long temp = value;
int[] cnt_a = new int[10];
// cnt_a has count of decimal digits in kth
// power of 2
while (temp > 0) {
long remainder = (temp % 10);
cnt_a[(int)remainder]++;
temp /= 10;
}
// checking if a power of 2 present in string s
bool fl = true;
for (int i = 0; i < 10; i++) {
if (cnt_a[i] > cnt_s[i]) {
fl = false;
break;
}
}
// if the power of 2 present in s we add it to
// ans
if (fl) {
ans.Add(value);
}
value *= 2;
}
Console.WriteLine(
"THE TOTAL POSSIBLE COMBINATIONS THAT ARE POWER OF 2 ARE: "
+ ans.Count);
foreach(long i in ans) { Console.WriteLine(i); }
}
// Driver code
public static void Main(string[] args)
{
string s = "614";
int n = s.Length;
calculatePower(s, n);
}
}
// This code is contributed by ukasp.
Javascript
<script>
function calculatePower(s,n)
{
// cnt_s is stores the count of each decimal digits of string s
let cnt_s = new Array(10).fill(0)
// Here we calculate the count of each decimal digit of string s
for(let i of s)
cnt_s[parseInt(i)] += 1
// our main logic is to generate powers of 2 and
// store the count of decimal digit of powers
// of 2 in cnt_a i.e we check for every i in
// range(0,10): if(cnt_s[i]>=cnt_[a])
let one = 1
let value = 2
let maxvalue = (one<<62)
let ans = []
// maxval has max power of 2 in range of long
// in this loop we generate powers of 2
while(value <= maxvalue){
// cnt_a has count of decimal digits in kth power of 2
let cnt_a = new Array(10).fill(0)
let fl = true
let temp = value
while(temp>0){
let remainder=temp%10
cnt_a[remainder]+=1
temp=parseInt(temp/10)
}
// checking if a power of 2 present in string s
for(let i=0;i<10;i++){
if(cnt_a[i]>cnt_s[i]){
fl=false
break
}
}
// if the power of 2 present in s we add it to ans
if(fl)
ans.push(value)
value*=2
}
document.write("THE TOTAL POSSIBLE COMBINATIONS THAT ARE POWER OF 2 ARE: ",ans.length,"</br>")
for(let i of ans)
document.write(i,"</br>")
}
// driver code
let s = "614"
let n = s.length
calculatePower(s,n)
// This code is contributed by shinjanpatra
</script>
COMPLEJIDAD DE TIEMPO: O (log (2 ^ 62) * N) donde N es la longitud de la string y log (2 ^ 62) porque 2 ^ 62 es la potencia máxima válida en el rango de
ESPACIO AUXILIAR largo: O (10 + 10)
Publicación traducida automáticamente
Artículo escrito por zack_aayush y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA