Permutaciones de un número dado que son potencias de 2

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:
      • Si arr[i] es igual a 0 , entonces continue .
      • De lo contrario, disminuya el valor de arr[i] en 1 y llame a la función compute(temp, “”) para encontrar las otras permutaciones posibles de la string str y sume el valor de arr[i] en 1 .
  • 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

Deja una respuesta

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