Given an array arr[] consisting of N unique elements, the task is to generate an array B[] of length N such that B[i] is the number of subsequences in which arr[i] is the maximum element.
Examples:
Input: arr[] = {2, 3, 1}
Output: {2, 4, 1}
Explanation: Subsequences in which arr[0] ( = 2) is maximum are {2}, {2, 1}.
Subsequences in which arr[1] ( = 3) is maximum are {3}, {1, 3, 2}, {2, 3}, {1, 3}.
Subsequence in which arr[2] ( = 1) is maximum is {1}.Input: arr[] = {23, 34, 12, 7, 15, 31}
Output: {8, 32, 2, 1, 4, 16}
Approach: The problem can be solved by observing that all the subsequences where an element, arr[i], will appear as the maximum will contain all the elements less than arr[i]. Therefore, the total number of distinct subsequences will be 2(Number of elements less than arr[i]). Follow the steps below to solve the problem:
- Sort the array arr[] indices with respect to their corresponding values present in the given array and store that indices in array indices[], where arr[indices[i]] < arr[indices[i+1]].
- Initialize an integer, subseq with 1 to store the number of possible subsequences.
- Iterate N times with pointer over the range [0, N-1] using a variable, i.
- B[indices[i]] is the number of subsequences in which arr[indices[i]] is maximum i.e., 2i, as there will be i elements less than arr[indices[i]].
- Store the answer for B[indices[i]] as B[indices[i]] = subseq.
- Update subseq by multiplying it by 2.
- Print the elements of the array B[] as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to merge the subarrays// arr[l .. m] and arr[m + 1, .. r]// based on indices[]void merge(int* indices, int* a, int l, int mid, int r){ int temp_ind[r - l + 1], j = mid + 1; int i = 0, temp_l = l, k; while (l <= mid && j <= r) { // If a[indices[l]] is less than // a[indices[j]], add indice[l] to temp if (a[indices[l]] < a[indices[j]]) temp_ind[i++] = indices[l++]; // Else add indices[j] else temp_ind[i++] = indices[j++]; } // Add remaining elements while (l <= mid) temp_ind[i++] = indices[l++]; // Add remaining elements while (j <= r) temp_ind[i++] = indices[j++]; for (k = 0; k < i; k++) indices[temp_l++] = temp_ind[k];}// Recursive function to divide// the array into partsvoid divide(int* indices, int* a, int l, int r){ if (l >= r) return; int mid = l / 2 + r / 2; // Recursive call for elements before mid divide(indices, a, l, mid); // Recursive call for elements after mid divide(indices, a, mid + 1, r); // Merge the two sorted arrays merge(indices, a, l, mid, r);}// Function to find the number of// subsequences for each elementvoid noOfSubsequences(int arr[], int N){ int indices[N], i; for (i = 0; i < N; i++) indices[i] = i; // Sorting the indices according // to array arr[] divide(indices, arr, 0, N - 1); // Array to store output numbers int B[N]; // Initialize subseq int subseq = 1; for (i = 0; i < N; i++) { // B[i] is 2^i B[indices[i]] = subseq; // Doubling the subsequences subseq *= 2; } // Print the final output, array B[] for (i = 0; i < N; i++) cout << B[i] << " ";}// Driver Codeint main(){ // Given array int arr[] = { 2, 3, 1 }; // Given length int N = sizeof(arr) / sizeof(arr[0]); // Function call noOfSubsequences(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to merge the subarrays// arr[l .. m] and arr[m + 1, .. r]// based on indices[]static void merge(int[] indices, int[] a, int l, int mid, int r){ int []temp_ind = new int[r - l + 1]; int j = mid + 1; int i = 0, temp_l = l, k; while (l <= mid && j <= r) { // If a[indices[l]] is less than // a[indices[j]], add indice[l] to temp if (a[indices[l]] < a[indices[j]]) temp_ind[i++] = indices[l++]; // Else add indices[j] else temp_ind[i++] = indices[j++]; } // Add remaining elements while (l <= mid) temp_ind[i++] = indices[l++]; // Add remaining elements while (j <= r) temp_ind[i++] = indices[j++]; for(k = 0; k < i; k++) indices[temp_l++] = temp_ind[k];}// Recursive function to divide// the array into partsstatic void divide(int[] indices, int[] a, int l, int r){ if (l >= r) return; int mid = l / 2 + r / 2; // Recursive call for elements before mid divide(indices, a, l, mid); // Recursive call for elements after mid divide(indices, a, mid + 1, r); // Merge the two sorted arrays merge(indices, a, l, mid, r);}// Function to find the number of// subsequences for each elementstatic void noOfSubsequences(int arr[], int N){ int []indices = new int[N]; int i; for(i = 0; i < N; i++) indices[i] = i; // Sorting the indices according // to array arr[] divide(indices, arr, 0, N - 1); // Array to store output numbers int[] B = new int[N]; // Initialize subseq int subseq = 1; for(i = 0; i < N; i++) { // B[i] is 2^i B[indices[i]] = subseq; // Doubling the subsequences subseq *= 2; } // Print the final output, array B[] for(i = 0; i < N; i++) System.out.print(B[i] + " ");}// Driver Codepublic static void main(String[] args){ // Given array int arr[] = { 2, 3, 1 }; // Given length int N = arr.length; // Function call noOfSubsequences(arr, N);}}// This code is contributed by Princi Singh |
Python3
# Python3 program for the above approach# Function to merge the subarrays# arr[l .. m] and arr[m + 1, .. r]# based on indices[]def merge(indices, a, l, mid, r): temp_ind = [0] * (r - l + 1) j = mid + 1 i = 0 temp_l = l while (l <= mid and j <= r): # If a[indices[l]] is less than # a[indices[j]], add indice[l] to temp if (a[indices[l]] < a[indices[j]]): temp_ind[i] = indices[l] i += 1 l += 1 # Else add indices[j] else: temp_ind[i] = indices[j] i += 1 j += 1 # Add remaining elements while (l <= mid): temp_ind[i] = indices[l] i += 1 l += 1 # Add remaining elements while (j <= r): temp_ind[i] = indices[j] i += 1 j += 1 for k in range(i): indices[temp_l] = temp_ind[k] temp_l += 1# Recursive function to divide# the array into partsdef divide(indices, a, l, r): if (l >= r): return mid = l // 2 + r // 2 # Recursive call for elements # before mid divide(indices, a, l, mid) # Recursive call for elements # after mid divide(indices, a, mid + 1, r) # Merge the two sorted arrays merge(indices, a, l, mid, r)# Function to find the number of# subsequences for each elementdef noOfSubsequences(arr, N): indices = N * [0] for i in range(N): indices[i] = i # Sorting the indices according # to array arr[] divide(indices, arr, 0, N - 1) # Array to store output numbers B = [0] * N # Initialize subseq subseq = 1 for i in range(N): # B[i] is 2^i B[indices[i]] = subseq # Doubling the subsequences subseq *= 2 # Print the final output, array B[] for i in range(N): print(B[i], end = " ")# Driver Codeif __name__ == "__main__": # Given array arr = [ 2, 3, 1 ] # Given length N = len(arr) # Function call noOfSubsequences(arr, N)# This code is contributed by chitranayal |
C#
// C# program for the above approachusing System;class GFG{// Function to merge the subarrays// arr[l .. m] and arr[m + 1, .. r]// based on indices[]static void merge(int[] indices, int[] a, int l, int mid, int r){ int []temp_ind = new int[r - l + 1]; int j = mid + 1; int i = 0, temp_l = l, k; while (l <= mid && j <= r) { // If a[indices[l]] is less than // a[indices[j]], add indice[l] to temp if (a[indices[l]] < a[indices[j]]) temp_ind[i++] = indices[l++]; // Else add indices[j] else temp_ind[i++] = indices[j++]; } // Add remaining elements while (l <= mid) temp_ind[i++] = indices[l++]; // Add remaining elements while (j <= r) temp_ind[i++] = indices[j++]; for(k = 0; k < i; k++) indices[temp_l++] = temp_ind[k];}// Recursive function to divide// the array into partsstatic void divide(int[] indices, int[] a, int l, int r){ if (l >= r) return; int mid = l / 2 + r / 2; // Recursive call for elements before mid divide(indices, a, l, mid); // Recursive call for elements after mid divide(indices, a, mid + 1, r); // Merge the two sorted arrays merge(indices, a, l, mid, r);}// Function to find the number of// subsequences for each elementstatic void noOfSubsequences(int []arr, int N){ int []indices = new int[N]; int i; for(i = 0; i < N; i++) indices[i] = i; // Sorting the indices according // to array []arr divide(indices, arr, 0, N - 1); // Array to store output numbers int[] B = new int[N]; // Initialize subseq int subseq = 1; for(i = 0; i < N; i++) { // B[i] is 2^i B[indices[i]] = subseq; // Doubling the subsequences subseq *= 2; } // Print the readonly output, array []B for(i = 0; i < N; i++) Console.Write(B[i] + " ");}// Driver Codepublic static void Main(String[] args){ // Given array int []arr = { 2, 3, 1 }; // Given length int N = arr.Length; // Function call noOfSubsequences(arr, N);}}// This code is contributed by Amit Katiyar |
Javascript
<script>// JavaScript program for the above approach// Function to merge the subarrays// arr[l .. m] and arr[m + 1, .. r]// based on indices[]function merge(indices, a, l, mid, r){ let temp_ind = []; let j = mid + 1; let i = 0, temp_l = l, k; while (l <= mid && j <= r) { // If a[indices[l]] is less than // a[indices[j]], add indice[l] to temp if (a[indices[l]] < a[indices[j]]) temp_ind[i++] = indices[l++]; // Else add indices[j] else temp_ind[i++] = indices[j++]; } // Add remaining elements while (l <= mid) temp_ind[i++] = indices[l++]; // Add remaining elements while (j <= r) temp_ind[i++] = indices[j++]; for(k = 0; k < i; k++) indices[temp_l++] = temp_ind[k];} // Recursive function to divide// the array into partsfunction divide(indices, a, l, r){ if (l >= r) return; let mid = l / 2 + r / 2; // Recursive call for elements before mid divide(indices, a, l, mid); // Recursive call for elements after mid divide(indices, a, mid + 1, r); // Merge the two sorted arrays merge(indices, a, l, mid, r);} // Function to find the number of// subsequences for each elementfunction noOfSubsequences(arr, N){ let indices = []; let i; for(i = 0; i < N; i++) indices[i] = i; // Sorting the indices according // to array arr[] divide(indices, arr, 0, N - 1); // Array to store output numbers let B = []; // Initialize subseq let subseq = 1; for(i = 0; i < N; i++) { // B[i] is 2^i B[indices[i]] = subseq; // Doubling the subsequences subseq *= 2; } // Print the final output, array B[] for(i = 0; i < N; i++) document.write(B[i] + " ");}// Driver code// Given arraylet arr = [ 2, 3, 1 ];// Given lengthlet N = arr.length;// Function callnoOfSubsequences(arr, N);// This code is contributed by avijitmondal1998</script> |
Output:
2 4 1
Time Complexity: O(NlogN) where N is the length of the given array.
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!
