Given an array of N distinct integers. For each element the task is to find the count of subsequence from all the possible subsequence whose minimum element is the current element.
Examples:
Input: arr[] = {1, 2}
Output: 2 1
Explanation:
Subsequences are {1}, {2}, {1, 2}.
The count of the smallest element in each subsequence is:
1 = 2, 2 = 1
Input: arr[] = {1, 2, 3}
Output: 4 2 1
Naive Approach: The idea is to generate all possible subsequences of the given array and count the smallest element in each subsequence and print its count for each element in the array.
Time Complexity: O(2N)
Auxiliary Space: O(N)
Efficient Approach: The idea is to observe a pattern i.e., so observe that minimum element occurs 2n – 1 times, the second minimum occurs 2n – 2 times and so on …. For Example:
Let the array be arr[] = {1, 2, 3}
Subsequences are {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}
Minimum of each subsequence: {1}, {2}, {3}, {1}, {1}, {2}, {1}.
where
1 occurs 4 times i.e. 2n – 1 where n = 3.
2 occurs 2 times i.e. 2n – 2 where n = 3.
3 occurs 1 times i.e. 2n – 3 where n = 3.
Below are the steps:
- Store the index of each element in a Map such that we can print the element in the order of the original array.
- Sort the given array.
- Now the elements are in increasing order and from the above observation traverse the given array and keep the count of subsequence such that each element is the smallest element is given by pow(2, N – 1 – i).
- Now traverse the map and print count of subsequence according to the element in the original array.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function that count the subsequence// such that each element as the// minimum element in the subsequencevoid solve(int arr[], int N){ map<int, int> M; // Store index in a map for (int i = 0; i < N; i++) { M[i] = arr[i]; } // Sort the array sort(arr, arr + N); // To store count of subsequence unordered_map<int, int> Count; // Traverse the array for (int i = 0; i < N; i++) { // Store count of subsequence Count[arr[i]] = pow(2, N - i - 1); } // Print the count of subsequence for (auto& it : M) { cout << Count[M[it.second]] << ' '; }}// Driver codeint main(){ int arr[] = { 5, 2, 1 }; int N = sizeof arr / sizeof arr[0]; // Function call solve(arr, N);} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function that count the subsequence// such that each element as the// minimum element in the subsequencestatic void solve(int arr[], int N){ HashMap<Integer, Integer> M = new HashMap<>(); // Store index in a map for (int i = 0; i < N; i++) { M.put(i, arr[i]); } // Sort the array Arrays.sort(arr); // To store count of subsequence HashMap<Integer, Integer> Count = new HashMap<>(); // Traverse the array for (int i = 0; i < N; i++) { // Store count of subsequence Count.put(arr[i], (int)Math.pow(2, N - i - 1)); } // Print the count of subsequence for (Map.Entry<Integer, Integer> m : M.entrySet()) { System.out.print(Count.get(m.getValue()) + " "); }}// Driver codepublic static void main(String[] args){ int arr[] = { 5, 2, 1 }; int N = arr.length; // Function call solve(arr, N);}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above approach# Function that count the subsequence# such that each element as the# minimum element in the subsequencedef solve(arr, N): M = {} # Store index in a map for i in range(N): M[i] = arr[i] # Sort the array arr.sort() # To store count of subsequence Count = {} # Traverse the array for i in range(N): # Store count of subsequence Count[arr[i]] = pow(2, N - i - 1) # Print the count of subsequence for it in Count.values(): print(it, end = " ")# Driver codeif __name__ == "__main__": arr = [ 5, 2, 1 ] N = len(arr) # Function call solve(arr, N)# This code is contributed by chitranayal |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function that count the subsequence// such that each element as the// minimum element in the subsequencestatic void solve(int []arr, int N){ Dictionary<int, int> M = new Dictionary<int, int>(); // Store index in a map for (int i = 0; i < N; i++) { M.Add(i, arr[i]); } // Sort the array Array.Sort(arr); // To store count of subsequence Dictionary<int, int> Count = new Dictionary<int, int>(); // Traverse the array for (int i = 0; i < N; i++) { // Store count of subsequence Count.Add(arr[i], (int)Math.Pow(2, N - i - 1)); } // Print the count of subsequence foreach(KeyValuePair<int, int> m in M){ Console.Write(Count[m.Value]); } }// Driver codepublic static void Main(String[] args){ int []arr = { 5, 2, 1 }; int N = arr.Length; // Function call solve(arr, N);}}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// Javascript program for the above approach// Function that count the subsequence// such that each element as the// minimum element in the subsequencefunction solve(arr, N){ var M = new Map(); // Store index in a map for (var i = 0; i < N; i++) { M.set(i, arr[i]); } // Sort the array arr.sort((a,b)=>a-b); // To store count of subsequence var Count = new Map(); // Traverse the array for (var i = 0; i < N; i++) { // Store count of subsequence Count.set(arr[i], parseInt(Math.pow(2, N - i - 1))); } // Print the count of subsequence M.forEach((value, key) => { document.write(Count.get(value) + ' '); }); }// Driver codevar arr = [5, 2, 1];var N = arr.length;// Function callsolve(arr, N);// This code is contributed by rrrtnx.</script> |
4 2 1
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
