Given an array A containing N positive integers, the task is to find the number of subsequences of this array such that in each subsequence , no digit is repeated twice, i.e. all the digits of the subsequences must be unique.
Examples:
Input: A = [1, 12, 23, 34]
Output: 7
The subsequences are: {1}, {12}, {23}, {34}, {1, 23}, {1, 34}, {12, 34}
Therefore the count of such subsequences = 7Input: A = [5, 12, 2, 1, 165, 2323, 7]
Output: 33
Naive approach: Generate all subsequences of the array and traverse through them to check whether the given condition is satisfied or not. Print the count of such subsequences at the end.
Below is the implementation of the above approach:
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 digitsbool 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 uniqueint 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 codeint 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 digitsstatic 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 uniquestatic 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 codepublic 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 digitsdef 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 uniquedef 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 codeif __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 digitsusing System;using System.Collections.Generic;class GFG{// Function to check whether// the subarray has all unique digitsstatic 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 uniquestatic 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 codepublic 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 digitsfunction 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 uniquefunction 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 codelet N = 4;let A = [1, 12, 23, 34];document.write(numberOfSubarrays(A, N));// This code is contributed by gfgking</script> |
Output:
7
Time Complexity: O(N * 2N)
Efficient Approach: This approach depends upon the fact that there exist only 10 unique digits in the Decimal number system. Therefore the longest subsequence will have only 10 digits in it, to meet the required condition.
- We will use Bitmasking and Dynamic Programming to solve the problem.
- Since there are only 10 digits, consider a 10-bit representation of every number where each bit is 1 if digit corresponding to that bit is present in that number.
- Let, i be the current array element (elements from 1 to i-1 are already processed). An integer variable ‘mask‘ indicates the digits which have already occurred in the subsequence. If i’th bit is set in the mask, then i’th digit has occurred, else not.
- At each step of recurrence relation, the element can either be included in the subsequence or not. If the element is not included in the subarray, then simply move to the next index. If it is included, change the mask by setting all the bits corresponding to the current element’s digit, ON in the mask.
Note: The current element can only be included if all of its digits have not occurred previously. - This condition will be satisfied only if the bits corresponding to the current element’s digits in the mask are OFF.
- If we draw the complete recursion tree, we can observe that many subproblems are being solved again and again. So we use Dynamic Programming. A table dp[][] is used such that for every index dp[i][j], i is the position of the element in the array and j is the mask.
Below is the implementation of the above approach:
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 tableint dp[5000][(1 << 10) + 5];// Function to obtain// the mask for any integerint 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 waysint 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 uniqueint numberOfSubarrays(int a[], int n){ // initializing dp memset(dp, -1, sizeof(dp)); return countWays(0, 0, a, n);}// Driver codeint 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 digitsimport java.util.*;class GFG{ // Dynamic programming tablestatic int [][]dp = new int[5000][(1 << 10) + 5]; // Function to obtain// the mask for any integerstatic 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 waysstatic 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 uniquestatic 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 codepublic 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 CodeN = 4A = [ 1, 12, 23, 34 ]rows = 5000cols = 1100# Initializing dpdp = [ [ -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 digitsusing System;public class GFG{// Dynamic programming tablestatic int [,]dp = new int[5000, (1 << 10) + 5];// Function to obtain// the mask for any integerstatic 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 waysstatic 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 uniquestatic 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 codepublic 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 tablevar dp = Array.from(Array(5000), ()=>Array((1 << 10) + 5).fill(-1));// Function to obtain// the mask for any integerfunction 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 waysfunction 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 uniquefunction numberOfSubarrays(a, n){ // initializing dp dp = Array.from(Array(5000), ()=>Array((1 << 10) + 5).fill(-1)); return countWays(0, 0, a, n);}// Driver codevar N = 4;var A = [1, 12, 23, 34];document.write( numberOfSubarrays(A, N));</script> |
Output:
7
Time Complexity: O(N * 210)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
