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:
- 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