Given an array A[] consisting of N integers, the task is to find the total number of subsequence which contain only one distinct number repeated throughout the subsequence.
Examples:
Input: A[] = {1, 2, 1, 5, 2}
Output: 7
Explanation:
Subsequences {1}, {2}, {1}, {5}, {2}, {1, 1} and {2, 2} satisfy the required conditions.Input: A[] = {5, 4, 4, 5, 10, 4}
Output: 11
Explanation:
Subsequences {5}, {4}, {4}, {5}, {10}, {4}, {5, 5}, {4, 4}, {4, 4}, {4, 4} and {4, 4, 4} satisfy the required conditions.
Approach:
Follow the steps below to solve the problem:
- Iterate over the array and calculate the frequency of each element in a HashMap.
- Traverse the HashMap. For each element, calculate the number of desired subsequences possible by the equation:
Number of subsequences possible by arr[i] = 2freq[arr[i]] – 1
- Calculate the total possible subsequences from the given array.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to count subsequences in // array containing same element void CountSubSequence(int A[], int N) { // Stores the count // of subsequences int result = 0; // Stores the frequency // of array elements map<int, int> mp; for (int i = 0; i < N; i++) { // Update frequency of A[i] mp[A[i]]++; } for (auto it : mp) { // Calculate number of subsequences result = result + pow(2, it.second) - 1; } // Print the result cout << result << endl; } // Driver code int main() { int A[] = { 5, 4, 4, 5, 10, 4 }; int N = sizeof(A) / sizeof(A[0]); CountSubSequence(A, N); return 0; } |
Java
// Java program to implement // the above approach import java.util.*;class GFG{// Function to count subsequences in// array containing same elementstatic void CountSubSequence(int A[], int N){ // Stores the count // of subsequences int result = 0; // Stores the frequency // of array elements Map<Integer, Integer> mp = new HashMap<Integer, Integer>(); for(int i = 0; i < N; i++) { // Update frequency of A[i] mp.put(A[i], mp.getOrDefault(A[i], 0) + 1); } for(Integer it : mp.values()) { // Calculate number of subsequences result = result + (int)Math.pow(2, it) - 1; } // Print the result System.out.println(result);}// Driver codepublic static void main(String[] args){ int A[] = { 5, 4, 4, 5, 10, 4 }; int N = A.length; CountSubSequence(A, N);}}// This code is contributed by offbeat |
Python3
# Python3 program to implement # the above approach # Function to count subsequences in # array containing same element def CountSubSequence(A, N): # Stores the frequency # of array elements mp = {} for element in A: if element in mp: mp[element] += 1 else: mp[element] = 1 result = 0 for key, value in mp.items(): # Calculate number of subsequences result += pow(2, value) - 1 # Print the result print(result)# Driver codeA = [ 5, 4, 4, 5, 10, 4 ]N = len(A)CountSubSequence(A, N)# This code is contributed by jojo9911 |
C#
// C# program to implement // the above approach using System;using System.Collections.Generic;class GFG{ // Function to count subsequences in // array containing same element public static void CountSubSequence(int []A, int N) { // Stores the count // of subsequences int result = 0; // Stores the frequency // of array elements var mp = new Dictionary<int, int>(); for(int i = 0; i < N; i++) { // Update frequency of A[i] if(mp.ContainsKey(A[i])) mp[A[i]] += 1; else mp.Add(A[i], 1); } foreach(var it in mp) { // Calculate number of subsequences result = result + (int)Math.Pow(2, it.Value) - 1; } // Print the result Console.Write(result); } // Driver code public static void Main() { int []A = { 5, 4, 4, 5, 10, 4 }; int N = A.Length; CountSubSequence(A, N); } } // This code is contributed by grand_master |
Javascript
<script>// Javascript program to implement // the above approach// Function to count subsequences in // array containing same element function CountSubSequence(A, N) { // Stores the count // of subsequences var result = 0; // Stores the frequency // of array elements var mp = new Map(); for (var i = 0; i < N; i++) { // Update frequency of A[i] if(mp.has(A[i])) mp.set(A[i], mp.get(A[i])+1) else mp.set(A[i], 1) } mp.forEach((value, key) => { // Calculate number of subsequences result = result + Math.pow(2, value) - 1; }); // Print the result document.write( result ); } // Driver code var A = [5, 4, 4, 5, 10, 4]; var N = A.length; CountSubSequence(A, N); // This code is contributed by itsok.</script> |
Output:
11
Time Complexity: O(NlogN)
Auxiliary Space: O(N)
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!
