Recuento de subsecuencias únicas de un número dado que son potencia de 2

Dada una string S de tamaño N y que contiene dígitos en el rango [0-9] , la tarea es imprimir el recuento de todas las subsecuencias únicas de una string que son la potencia de 2 .

Ejemplos:

Entrada: S = “1216389”
Salida: 5
Explicación:
Todas las subsecuencias únicas posibles que son potencia de 2 son: {1, 2, 16, 128, 8}

Entrada: S = “12”
Salida: 2
Explicación:
Todas las posibles subsecuencias únicas que son potencia de 2 son: {1, 2}.

Enfoque: el problema se puede resolver generando todas las subsecuencias de la string S y luego verificando si el número es la potencia de 2 o no. Siga los pasos a continuación para resolver el problema:

  • Inicialice un conjunto , por ejemplo, allUniqueSubSeq para almacenar la subsecuencia, que es una potencia de 2 .
  • Defina una función recursiva , diga uniqueSubSeq(S, ans, index) y realice los siguientes pasos:
    • Caso base: si el índice es igual a N, entonces si, (int)ans, es la potencia de 2 , entonces inserte ans en el conjunto allUniqueSubSeq .
    • De lo contrario, hay dos casos:
      • Si se agrega S[index] en la string ans , entonces recupere la función uniqueSubSeq con los parámetros S , ans + S[index] e index+1.
      • Si S[index] no se agrega en la string ans , recupere la función uniqueSubSeq con los parámetros S , ans e index + 1 .
  • Finalmente, después de realizar los pasos anteriores, llame a la función, uniqueSubSeq(S, “”, 0) y luego imprima allUniqueSubSeq.size() como la respuesta.

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Set to store subsequences that are
// power of 2
unordered_set<string> allUniqueSubSeq;
 
// Function to check whether the number
// is power of 2 or not
bool checkpower(int n)
{
    if ((n & (n - 1)) == 0)
    {
        return true;
    }
    return false;
}
 
// Auxiliary recursive Function to find
// all the unique subsequences of a string
// that are the power of 2
void uniqueSubSeq(string S, int N, string ans,
                            int index)
{
     
    // If index is equal to N
    if (index == N)
    {
        if (ans.length() != 0)
 
            // If the number is
            // power of 2
            if (checkpower(stoi(ans)))
            {
                 
                // Insert the String
                // in the set
                allUniqueSubSeq.insert(ans);
            }
        return;
    }
 
    // Recursion call, if the S[index]
    // is inserted in ans
    uniqueSubSeq(S, N, ans + S[index], index + 1);
 
    // Recursion call, if S[index] is
    // not inserted in ans
    uniqueSubSeq(S, N, ans, index + 1);
}
 
// Function to find count of all the unique
// subsequences of a string that are the
// power of 2
int Countsubsequneces(string S, int N)
{
     
    // Function Call
    uniqueSubSeq(S, N, "", 0);
 
    // Return the length of set
    // allUniqueSubSeq
    return allUniqueSubSeq.size();
}
 
// Driver Code
int main()
{
     
    // Given Input
    string S = "1216389";
    int N = S.length();
     
    // Function call
    cout << Countsubsequneces(S, N);
     
    return 0;
}
 
// This code is contributed by maddler

Java

// Java program for the above approach
import java.io.*;
import java.util.*;
public class main {
 
    // Set to store subsequences that are
    // power of 2
    static HashSet<String> allUniqueSubSeq
        = new HashSet<>();
 
    // Function to check whether the number
    // is power of 2 or not
    static boolean checkpower(int n)
    {
        if ((n & (n - 1)) == 0) {
            return true;
        }
        return false;
    }
 
    // Auxiliary recursive Function to find
    // all the unique subsequences of a string
    // that are the power of 2
    static void uniqueSubSeq(String S, int N, String ans,
                             int index)
    {
 
        // If index is equal to N
        if (index == N) {
 
            if (ans.length() != 0)
 
                // If the number is
                // power of 2
                if (checkpower(
                        Integer.parseInt(ans.trim()))) {
 
                    // Insert the String
                    // in the set
                    allUniqueSubSeq.add(ans);
                }
            return;
        }
 
        // Recursion call, if the S[index]
        // is inserted in ans
        uniqueSubSeq(S, N, ans + S.charAt(index),
                     index + 1);
 
        // Recursion call, if S[index] is
        // not inserted in ans
        uniqueSubSeq(S, N, ans, index + 1);
    }
 
    // Function to find count of all the unique
    // subsequences of a string that are the
    // power of 2
    static int Countsubsequneces(String S, int N)
    {
        // Function Call
        uniqueSubSeq(S, N, "", 0);
 
        // Return the length of set
        // allUniqueSubSeq
        return allUniqueSubSeq.size();
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        // Given Input
        String S = "1216389";
        int N = S.length();
 
        // Function call
        System.out.println(Countsubsequneces(S, N));
    }
}

Python3

# Python program for the above approach
 
# Set to store subsequences that are
# power of 2
allUniqueSubSeq = set()
 
# Function to check whether the number
# is power of 2 or not
def checkpower(n):
    if(n & (n-1) == 0):
        return True
    return False
 
# Auxiliary recursive Function to find
# all the unique subsequences of a string
# that are the power of 2
def uniqueSubSeq(S, N, ans, index):
   
    # If index is equal to N
    if (index == N):
        if (len(ans) != 0):
           
            # If the number is
            # power of 2
            if(checkpower(int(ans))):
                allUniqueSubSeq.add(ans)
        return
       
    # Recursion call, if the S[index]
    # is inserted in ans
    uniqueSubSeq(S, N, ans+S[index], index+1)
     
    # Recursion call, if the S[index]
    # is not inserted in ans
    uniqueSubSeq(S, N, ans, index+1)
 
# Function to find count of all the unique
# subsequences of a string that are
# the power of 2
def countSubsequences(S, N):
   
    # Function call
    uniqueSubSeq(S, N, "", 0)
     
    # Return the length of set
    # allUniqueSubSeq
    return len(allUniqueSubSeq)
 
# Driver code
if __name__ == '__main__':
   
    # Given Input
    S = "1216389"
    N = len(S)
 
    # Function call
    print(countSubsequences(S, N))
     
# This code is contributed by MuskanKalra1

C#

using System;
using System.Collections.Generic;
public class GFG {
 
    // Set to store subsequences that are
    // power of 2
    static HashSet<String> allUniqueSubSeq
        = new HashSet<String>();
 
    // Function to check whether the number
    // is power of 2 or not
    static bool checkpower(int n)
    {
        if ((n & (n - 1)) == 0) {
            return true;
        }
        return false;
    }
 
    // Auxiliary recursive Function to find
    // all the unique subsequences of a string
    // that are the power of 2
    static void uniqueSubSeq(String S, int N, String ans,
                             int index)
    {
 
        // If index is equal to N
        if (index == N) {
 
            if (ans.Length != 0)
 
                // If the number is
                // power of 2
                if (checkpower(
                        int.Parse(ans))) {
 
                    // Insert the String
                    // in the set
                    allUniqueSubSeq.Add(ans);
                }
            return;
        }
 
        // Recursion call, if the S[index]
        // is inserted in ans
        uniqueSubSeq(S, N, ans + S[index],
                     index + 1);
 
        // Recursion call, if S[index] is
        // not inserted in ans
        uniqueSubSeq(S, N, ans, index + 1);
    }
 
    // Function to find count of all the unique
    // subsequences of a string that are the
    // power of 2
    static int Countsubsequeneces(String S, int N)
    {
        // Function Call
        uniqueSubSeq(S, N, "", 0);
 
        // Return the length of set
        // allUniqueSubSeq
        return allUniqueSubSeq.Count;
    }
 
    // Driver Code
 
    static public void Main()
    {
        String S = "1216389";
        int N = S.Length;
 
        // Function call
        Console.WriteLine(Countsubsequeneces(S, N));
    }
}
 
// This code is contributed by maddler.

Javascript

<script>
       // Javascript program for above approach
 
       // Set to store subsequences that are
       // power of 2
       const allUniqueSubSeq
           = new Set();
 
       // Function to check whether the number
       // is power of 2 or not
       function checkpower(n) {
           if ((n & (n - 1)) == 0) {
               return true;
           }
           return false;
       }
 
       // Auxiliary recursive Function to find
       // all the unique subsequences of a string
       // that are the power of 2
       function uniqueSubSeq(S, N, ans, index) {
 
           // If index is equal to N
           if (index == N) {
 
               if (ans.length != 0)
 
                   // If the number is
                   // power of 2
                   if (checkpower(parseInt(ans.trim()))) {
 
                       // Insert the String
                       // in the set
                       allUniqueSubSeq.add(ans);
                   }
               return;
           }
 
           // Recursion call, if the S[index]
           // is inserted in ans
           uniqueSubSeq(S, N, ans + S.charAt(index),
               index + 1);
 
           // Recursion call, if S[index] is
           // not inserted in ans
           uniqueSubSeq(S, N, ans, index + 1);
       }
 
       // Function to find count of all the unique
       // subsequences of a string that are the
       // power of 2
       function Countsubsequneces(S, N) {
           // Function Call
           uniqueSubSeq(S, N, "", 0);
 
           // Return the length of set
           // allUniqueSubSeq
           return allUniqueSubSeq.size;
       }
 
       // Driver Code
 
       // Given Input
       let S = "1216389";
       let N = S.length;
 
       // Function call
       document.write(Countsubsequneces(S, N));
 
       // This code is contributed by Hritik
   </script>
Producción

5

Complejidad de Tiempo: O(2 N )
Espacio Auxiliar: O(2 N )

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 *