Dada una array A que contiene N enteros positivos, la tarea es encontrar el número de subsecuencias de esta array tal que en cada subsecuencia ningún dígito se repita dos veces, es decir, todos los dígitos de las subsecuencias deben ser únicos.
Ejemplos:
Entrada: A = [1, 12, 23, 34]
Salida: 7
Las subsecuencias son: {1}, {12}, {23}, {34}, {1, 23}, {1, 34}, {12 , 34}
Por lo tanto, la cuenta de tales subsecuencias = 7Entrada: A = [5, 12, 2, 1, 165, 2323, 7]
Salida: 33
Enfoque ingenuo: genere todas las subsecuencias de la array y recórralas para verificar si la condición dada se cumple o no. Imprime el recuento de dichas subsecuencias al final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the count
// of subsequences of an Array
// having all unique digits
#include <bits/stdc++.h>
using namespace std;
// Function to check whether
// the subsequences has all unique digits
bool check(vector<int>& v)
{
// Storing all digits occurred
set<int> digits;
// Traversing all the numbers of v
for (int i = 0; i < v.size(); i++) {
// Storing all digits of v[i]
set<int> d;
while (v[i]) {
d.insert(v[i] % 10);
v[i] /= 10;
}
// Checking whether digits of v[i]
// have already occurred
for (auto it : d) {
if (digits.count(it))
return false;
}
// Inserting digits of v[i] in the set
for (auto it : d)
digits.insert(it);
}
return true;
}
// Function to count the number
// subarray with all digits unique
int numberOfSubarrays(int a[], int n)
{
int answer = 0;
// Traverse through all the subarrays
for (int i = 1; i < (1 << n); i++) {
// To store elements of this subarray
vector<int> temp;
// Generate all subarray
// and store it in vector
for (int j = 0; j < n; j++) {
if (i & (1 << j))
temp.push_back(a[j]);
}
// Check whether this subarray
// has all digits unique
if (check(temp))
// Increase the count
answer++;
}
// Return the count
return answer;
}
// Driver code
int main()
{
int N = 4;
int A[] = { 1, 12, 23, 34 };
cout << numberOfSubarrays(A, N);
return 0;
}
Java
// Java program to find the count
// of subarrays of an Array
// having all unique digits
import java.util.*;
class GFG{
// Function to check whether
// the subarray has all unique digits
static boolean check(Vector<Integer> v)
{
// Storing all digits occurred
HashSet<Integer> digits = new HashSet<Integer>();
// Traversing all the numbers of v
for (int i = 0; i < v.size(); i++) {
// Storing all digits of v[i]
HashSet<Integer> d = new HashSet<Integer>();
while (v.get(i)>0) {
d.add(v.get(i) % 10);
v.set(i, v.get(i)/10);
}
// Checking whether digits of v[i]
// have already occurred
for (int it : d) {
if (digits.contains(it))
return false;
}
// Inserting digits of v[i] in the set
for (int it : d)
digits.add(it);
}
return true;
}
// Function to count the number
// subarray with all digits unique
static int numberOfSubarrays(int a[], int n)
{
int answer = 0;
// Traverse through all the subarrays
for (int i = 1; i < (1 << n); i++) {
// To store elements of this subarray
Vector<Integer> temp = new Vector<Integer>();
// Generate all subarray
// and store it in vector
for (int j = 0; j < n; j++) {
if ((i & (1 << j))>0)
temp.add(a[j]);
}
// Check whether this subarray
// has all digits unique
if (check(temp))
// Increase the count
answer++;
}
// Return the count
return answer;
}
// Driver code
public static void main(String[] args)
{
int N = 4;
int A[] = { 1, 12, 23, 34 };
System.out.print(numberOfSubarrays(A, N));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to find the count # of subarrays of an Array # having all unique digits # Function to check whether # the subarray has all unique digits def check(v): # Storing all digits occurred digits = set() # Traversing all the numbers of v for i in range(len(v)): # Storing all digits of v[i] d = set() while (v[i] != 0): d.add(v[i] % 10) v[i] //= 10 # Checking whether digits of v[i] # have already occurred for it in d: if it in digits: return False # Inserting digits of v[i] in the set for it in d: digits.add(it) return True # Function to count the number # subarray with all digits unique def numberOfSubarrays(a, n): answer = 0 # Traverse through all the subarrays for i in range(1, 1 << n): # To store elements of this subarray temp = [] # Generate all subarray # and store it in vector for j in range(n): if (i & (1 << j)): temp.append(a[j]) # Check whether this subarray # has all digits unique if (check(temp)): # Increase the count answer += 1 # Return the count return answer # Driver code if __name__=="__main__": N = 4 A = [ 1, 12, 23, 34 ] print(numberOfSubarrays(A, N)) # This code is contributed by rutvik_56
C#
// C# program to find the count
// of subarrays of an Array
// having all unique digits
using System;
using System.Collections.Generic;
class GFG{
// Function to check whether
// the subarray has all unique digits
static bool check(List<int> v)
{
// Storing all digits occurred
HashSet<int> digits = new HashSet<int>();
// Traversing all the numbers of v
for(int i = 0; i < v.Count; i++)
{
// Storing all digits of v[i]
HashSet<int> d = new HashSet<int>();
while (v[i] > 0)
{
d.Add(v[i] % 10);
v[i] = v[i] / 10;
}
// Checking whether digits of v[i]
// have already occurred
foreach(int it in d)
{
if (digits.Contains(it))
return false;
}
// Inserting digits of v[i] in the set
foreach(int it in d)
digits.Add(it);
}
return true;
}
// Function to count the number
// subarray with all digits unique
static int numberOfSubarrays(int []a, int n)
{
int answer = 0;
// Traverse through all the subarrays
for(int i = 1; i < (1 << n); i++)
{
// To store elements of this subarray
List<int> temp = new List<int>();
// Generate all subarray
// and store it in vector
for(int j = 0; j < n; j++)
{
if ((i & (1 << j)) > 0)
temp.Add(a[j]);
}
// Check whether this subarray
// has all digits unique
if (check(temp))
// Increase the count
answer++;
}
// Return the count
return answer;
}
// Driver code
public static void Main(String[] args)
{
int N = 4;
int []A = { 1, 12, 23, 34 };
Console.Write(numberOfSubarrays(A, N));
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// Javascript program to find the count
// of subarrays of an Array
// having all unique digits
// Function to check whether
// the subarray has all unique digits
function check(v) {
// Storing all digits occurred
let digits = new Set();
// Traversing all the numbers of v
for (let i = 0; i < v.length; i++) {
// Storing all digits of v[i]
let d = new Set();
while (v[i]) {
d.add(v[i] % 10);
v[i] = Math.floor(v[i] / 10);
}
// Checking whether digits of v[i]
// have already occurred
for (let it of d) {
if (digits.has(it))
return false;
}
// Inserting digits of v[i] in the set
for (let it of d)
digits.add(it);
}
return true;
}
// Function to count the number
// subarray with all digits unique
function numberOfSubarrays(a, n) {
let answer = 0;
// Traverse through all the subarrays
for (let i = 1; i < (1 << n); i++) {
// To store elements of this subarray
let temp = new Array();
// Generate all subarray
// and store it in vector
for (let j = 0; j < n; j++) {
if (i & (1 << j))
temp.push(a[j]);
}
// Check whether this subarray
// has all digits unique
if (check(temp))
// Increase the count
answer++;
}
// Return the count
return answer;
}
// Driver code
let N = 4;
let A = [1, 12, 23, 34];
document.write(numberOfSubarrays(A, N));
// This code is contributed by gfgking
</script>
Producción:
7
Complejidad del tiempo: O(N * 2 N )
Enfoque eficiente: este enfoque depende del hecho de que solo existen 10 dígitos únicos en el sistema numérico decimal. Por lo tanto, la subsecuencia más larga tendrá solo 10 dígitos para cumplir con la condición requerida.
- Usaremos Bitmasking y Programación Dinámica para resolver el problema.
- Dado que solo hay 10 dígitos, considere una representación de 10 bits de cada número donde cada bit es 1 si el dígito correspondiente a ese bit está presente en ese número.
- Sea i el elemento de array actual (los elementos del 1 al i-1 ya están procesados). Una variable entera ‘ máscara ‘ indica los dígitos que ya han ocurrido en la subsecuencia. Si se establece el i-ésimo bit en la máscara, entonces se ha producido el i-ésimo dígito, de lo contrario no.
- En cada paso de la relación de recurrencia , el elemento puede incluirse en la subsecuencia o no. Si el elemento no está incluido en el subarreglo, simplemente muévase al siguiente índice. Si está incluido, cambie la máscara poniendo en ON todos los bits correspondientes al dígito del elemento actual en la máscara.
Nota: El elemento actual solo se puede incluir si todos sus dígitos no se han producido previamente. - Esta condición se cumplirá solo si los bits correspondientes a los dígitos del elemento actual en la máscara están en OFF.
- Si dibujamos el árbol de recursión completo , podemos observar que muchos subproblemas se resuelven una y otra vez. Entonces usamos Programación Dinámica . Se usa una tabla dp[][] tal que para cada índice dp[i][j], i es la posición del elemento en el arreglo y j es la máscara.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the count
// of subsequences of an Array
// having all unique digits
#include <bits/stdc++.h>
using namespace std;
// Dynamic programming table
int dp[5000][(1 << 10) + 5];
// Function to obtain
// the mask for any integer
int getmask(int val)
{
int mask = 0;
if (val == 0)
return 1;
while (val) {
int d = val % 10;
mask |= (1 << d);
val /= 10;
}
return mask;
}
// Function to count the number of ways
int countWays(int pos, int mask,
int a[], int n)
{
// Subarray must not be empty
if (pos == n)
return (mask > 0 ? 1 : 0);
// If subproblem has been solved
if (dp[pos][mask] != -1)
return dp[pos][mask];
int count = 0;
// Excluding this element in the subarray
count = count
+ countWays(pos + 1, mask, a, n);
// If there are no common digits
// then only this element can be included
if ((getmask(a[pos]) & mask) == 0) {
// Calculate the new mask
// if this element is included
int new_mask
= (mask | (getmask(a[pos])));
count = count
+ countWays(pos + 1,
new_mask,
a, n);
}
// Store and return the answer
return dp[pos][mask] = count;
}
// Function to find the count of
// subarray with all digits unique
int numberOfSubarrays(int a[], int n)
{
// initializing dp
memset(dp, -1, sizeof(dp));
return countWays(0, 0, a, n);
}
// Driver code
int main()
{
int N = 4;
int A[] = { 1, 12, 23, 34 };
cout << numberOfSubarrays(A, N);
return 0;
}
Java
// Java program to find the count
// of subarrays of an Array
// having all unique digits
import java.util.*;
class GFG{
// Dynamic programming table
static int [][]dp = new int[5000][(1 << 10) + 5];
// Function to obtain
// the mask for any integer
static int getmask(int val)
{
int mask = 0;
if (val == 0)
return 1;
while (val > 0) {
int d = val % 10;
mask |= (1 << d);
val /= 10;
}
return mask;
}
// Function to count the number of ways
static int countWays(int pos, int mask,
int a[], int n)
{
// Subarray must not be empty
if (pos == n)
return (mask > 0 ? 1 : 0);
// If subproblem has been solved
if (dp[pos][mask] != -1)
return dp[pos][mask];
int count = 0;
// Excluding this element in the subarray
count = count
+ countWays(pos + 1, mask, a, n);
// If there are no common digits
// then only this element can be included
if ((getmask(a[pos]) & mask) == 0) {
// Calculate the new mask
// if this element is included
int new_mask
= (mask | (getmask(a[pos])));
count = count
+ countWays(pos + 1,
new_mask,
a, n);
}
// Store and return the answer
return dp[pos][mask] = count;
}
// Function to find the count of
// subarray with all digits unique
static int numberOfSubarrays(int a[], int n)
{
// initializing dp
for(int i = 0;i<5000;i++)
{
for (int j = 0; j < (1 << 10) + 5; j++) {
dp[i][j] = -1;
}
}
return countWays(0, 0, a, n);
}
// Driver code
public static void main(String[] args)
{
int N = 4;
int A[] = { 1, 12, 23, 34 };
System.out.print(numberOfSubarrays(A, N));
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program to find the count # of subarrays of an Array having all # unique digits # Function to obtain # the mask for any integer def getmask(val): mask = 0 if val == 0: return 1 while (val): d = val % 10; mask |= (1 << d) val = val // 10 return mask # Function to count the number of ways def countWays(pos, mask, a, n): # Subarray must not be empty if pos == n : if mask > 0: return 1 else: return 0 # If subproblem has been solved if dp[pos][mask] != -1: return dp[pos][mask] count = 0 # Excluding this element in the subarray count = (count + countWays(pos + 1, mask, a, n)) # If there are no common digits # then only this element can be included if (getmask(a[pos]) & mask) == 0: # Calculate the new mask # if this element is included new_mask = (mask | (getmask(a[pos]))) count = (count + countWays(pos + 1, new_mask, a, n)) # Store and return the answer dp[pos][mask] = count return count # Function to find the count of # subarray with all digits unique def numberOfSubarrays(a, n): return countWays(0, 0, a, n) # Driver Code N = 4 A = [ 1, 12, 23, 34 ] rows = 5000 cols = 1100 # Initializing dp dp = [ [ -1 for i in range(cols) ] for j in range(rows) ] print( numberOfSubarrays(A, N)) # This code is contributed by sarthak_eddy.
C#
// C# program to find the count
// of subarrays of an Array
// having all unique digits
using System;
public class GFG{
// Dynamic programming table
static int [,]dp = new int[5000, (1 << 10) + 5];
// Function to obtain
// the mask for any integer
static int getmask(int val)
{
int mask = 0;
if (val == 0)
return 1;
while (val > 0) {
int d = val % 10;
mask |= (1 << d);
val /= 10;
}
return mask;
}
// Function to count the number of ways
static int countWays(int pos, int mask,
int []a, int n)
{
// Subarray must not be empty
if (pos == n)
return (mask > 0 ? 1 : 0);
// If subproblem has been solved
if (dp[pos, mask] != -1)
return dp[pos, mask];
int count = 0;
// Excluding this element in the subarray
count = count
+ countWays(pos + 1, mask, a, n);
// If there are no common digits
// then only this element can be included
if ((getmask(a[pos]) & mask) == 0) {
// Calculate the new mask
// if this element is included
int new_mask
= (mask | (getmask(a[pos])));
count = count
+ countWays(pos + 1,
new_mask, a, n);
}
// Store and return the answer
return dp[pos, mask] = count;
}
// Function to find the count of
// subarray with all digits unique
static int numberOfSubarrays(int []a, int n)
{
// initializing dp
for(int i = 0; i < 5000; i++)
{
for (int j = 0; j < (1 << 10) + 5; j++) {
dp[i,j] = -1;
}
}
return countWays(0, 0, a, n);
}
// Driver code
public static void Main(String[] args)
{
int N = 4;
int []A = { 1, 12, 23, 34 };
Console.Write(numberOfSubarrays(A, N));
}
}
// This code contributed by sapnasingh4991
Javascript
<script>
// Javascript program to find the count
// of subarrays of an Array
// having all unique digits
// Dynamic programming table
var dp = Array.from(Array(5000), ()=>Array((1 << 10) + 5).fill(-1));
// Function to obtain
// the mask for any integer
function getmask(val)
{
var mask = 0;
if (val == 0)
return 1;
while (val) {
var d = val % 10;
mask |= (1 << d);
val = parseInt(val/10);
}
return mask;
}
// Function to count the number of ways
function countWays(pos, mask, a, n)
{
// Subarray must not be empty
if (pos == n)
return (mask > 0 ? 1 : 0);
// If subproblem has been solved
if (dp[pos][mask] != -1)
return dp[pos][mask];
var count = 0;
// Excluding this element in the subarray
count = count
+ countWays(pos + 1, mask, a, n);
// If there are no common digits
// then only this element can be included
if ((getmask(a[pos]) & mask) == 0) {
// Calculate the new mask
// if this element is included
var new_mask
= (mask | (getmask(a[pos])));
count = count
+ countWays(pos + 1,
new_mask,
a, n);
}
// Store and return the answer
return dp[pos][mask] = count;
}
// Function to find the count of
// subarray with all digits unique
function numberOfSubarrays(a, n)
{
// initializing dp
dp = Array.from(Array(5000), ()=>Array((1 << 10) + 5).fill(-1));
return countWays(0, 0, a, n);
}
// Driver code
var N = 4;
var A = [1, 12, 23, 34];
document.write( numberOfSubarrays(A, N));
</script>
Producción:
7
Complejidad de tiempo: O(N * 2 10 )