Given two arrays arr1[] and arr2[] of length M and N consisting of digits [0, 9] representing two numbers and an integer K(K ? M + N), the task is to find the maximum K-digit number possible by selecting subsequences from the given arrays such that the relative order of the digits is the same as in the given array.
Examples:
Input: arr1[] = {3, 4, 6, 5}, arr2[] = {9, 1, 2, 5, 8, 3}, K = 5
Output: 98653
Explanation: The maximum number that can be formed out of the given arrays arr1[] and arr2[] of length K is 98653.Input: arr1[] = {6, 7}, arr2[] = {6, 0, 4}, K = 5
Output: 67604
Explanation: The maximum number that can be formed out of the given arrays arr1[] and arr2[] of length K is 67604.
Naive Approach: The idea is to generate all subsequences of length s1 from arr1[] and all subsequences of length (K – s1) from the array arr2[] over all values of s1 in the range [0, K] and keep track of the maximum number so formed by merging both arrays in every iteration.
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to get the maximum number from the array arr1[] and of length s1 and maximum number from the array arr2[] and of length (K – s1). Then, merge the two arrays to get the maximum number of length K. Follow the steps below to solve the given problem:
- Iterate over the range [0, K] using the variable i and generate all possible decreasing subsequences of length i preserving the same order as in the array arr1[] and subsequences of length (K – i) following the same order as in the array arr2[].
- For generating decreasing subsequence of length L of any array arr[] in the above step do the following:
- Initialize an array ans[] to store the subsequences of length L preserving the same order as in arr[] and Traverse the array arr[] and do the following:
- Till the last element is less than the current element, then remove the last element from array ans[].
- If the length of ans[] is less than L then insert the current element in the ans[].
- After the above steps, the array ans[] in the resultant subsequence.
- Initialize an array ans[] to store the subsequences of length L preserving the same order as in arr[] and Traverse the array arr[] and do the following:
- While generating the subsequences of all possible length in Step 1 using the approach discussed in Step 2 generate the maximum number by merging the two subsequences formed.
- After the above steps, print that subsequence which gives maximum number after merging.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;void pop_front(std::vector<int> &v){ if (v.size() > 0) { v.erase(v.begin()); }}// Function to calculate maximum // number from nums of length c_lenvector<int> helper(vector<int> nums, int c_len){ // Store the resultant maximum vector<int> ans; // Length of the nums array int ln = nums.size(); // Traverse the nums array for(int i=0;i<ln;i++) { while(ans.size()>0 && ans.back()<nums[i] && ((ln-i) > (c_len-ans.size()))) // If true, then pop // out the last element ans.pop_back(); // Check the length with // required length if(ans.size()<c_len) // Append the value to ans ans.push_back(nums[i]); } // Return the ans return ans;}// Function to find maximum K-digit number// possible from subsequences of the// two arrays nums1[] and nums2[]vector<int> maxNumber(vector<int> nums1, vector<int> nums2,int k){ // Store lengths of the arrays int l1 = nums1.size(); int l2 = nums2.size(); // Store the resultant subsequence vector<int> rs; // Traverse and pick the maximum for(int s1=max(0, k-l2);s1<=min(k, l1);s1++) { // p1 and p2 stores maximum number possible // of length s1 and k - s1 from // the arrays nums1[] & nums2[] vector<int> p1,p2; p1 = helper(nums1, s1); p2 = helper(nums2, k-s1); // Update the maximum number vector<int> temp; for(int j=0;j<k;j++) { vector<int> temp2 = max(p1,p2); int fr = temp2.front(); if(p1>p2) pop_front(p1); else pop_front(p2); temp.push_back(fr); } rs = max(rs, temp); } // Return the result return rs;}// Driver Codeint main(){ vector<int> arr1{3, 4, 6, 5}; vector<int> arr2{9, 1, 2, 5, 8, 3}; int K=5; // Function Call vector<int> v = maxNumber(arr1, arr2, K); for(int i=0;i<v.size();i++) cout<<v[i]<<" "; return 0;}// This code is contributed by Pushpesh Raj |
Java
import java.util.*;import java.io.*;// Java program for the above approachclass GFG{ // Function to calculate maximum // number from nums of length c_len static ArrayList<Integer> helper(ArrayList<Integer> nums, int c_len) { // Store the resultant maximum ArrayList<Integer> ans = new ArrayList<Integer>(); // Length of the nums array int ln = nums.size(); // Traverse the nums array for(int i = 0 ; i < ln ; i++) { while(ans.size() > 0 && ans.get(ans.size() - 1) < nums.get(i) && ((ln-i) > (c_len - ans.size()))){ // If true, then pop // out the last element ans.remove(ans.size() - 1); } // Check the length with // required length if(ans.size() < c_len){ // Append the value to ans ans.add(nums.get(i)); } } // Return the ans return ans; } // Returns True if a1 is greater than a2 static boolean comp(ArrayList<Integer> a1, ArrayList<Integer> a2){ int s1 = a1.size(); int s2 = a2.size(); int i1 = 0, i2 = 0; while(i1 < s1 && i2 < s2){ if(a1.get(i1) > a2.get(i2)){ return true; }else if(a1.get(i1) < a2.get(i2)){ return false; } i1++; i2++; } if(i1 < s1) return true; return false; } // Function to find maximum K-digit number // possible from subsequences of the // two arrays nums1[] and nums2[] static ArrayList<Integer> maxNumber(ArrayList<Integer> nums1, ArrayList<Integer> nums2,int k) { // Store lengths of the arrays int l1 = nums1.size(); int l2 = nums2.size(); // Store the resultant subsequence ArrayList<Integer> rs = new ArrayList<Integer>(); // Traverse and pick the maximum for(int s1 = Math.max(0, k-l2) ; s1 <= Math.min(k, l1) ; s1++) { // p1 and p2 stores maximum number possible // of length s1 and k - s1 from // the arrays nums1[] & nums2[] ArrayList<Integer> p1 = new ArrayList<Integer>(); ArrayList<Integer> p2 = new ArrayList<Integer>(); p1 = helper(nums1, s1); p2 = helper(nums2, k-s1); // Update the maximum number ArrayList<Integer> temp = new ArrayList<Integer>(); for(int j = 0 ; j < k ; j++) { ArrayList<Integer> temp2 = comp(p1, p2) ? p1 : p2; int fr = temp2.get(0); if(comp(p1, p2)){ if(p1.size() > 0){ p1.remove(0); } }else{ if(p2.size() > 0){ p2.remove(0); } } temp.add(fr); } rs = comp(rs, temp) ? rs : temp; } // Return the result return rs; } public static void main(String args[]) { ArrayList<Integer> arr1 = new ArrayList<Integer>( List.of( 3, 4, 6, 5 ) ); ArrayList<Integer> arr2 = new ArrayList<Integer>( List.of( 9, 1, 2, 5, 8, 3 ) ); int K = 5; // Function Call ArrayList<Integer> v = maxNumber(arr1, arr2, K); for(int i = 0 ; i < v.size() ; i++){ System.out.print(v.get(i) + " "); } }}// This code is contributed by subhamgoyal2014. |
Python3
# Python program for the above approach# Function to find maximum K-digit number# possible from subsequences of the# two arrays nums1[] and nums2[]def maxNumber(nums1, nums2, k): # Store lengths of the arrays l1, l2 = len(nums1), len(nums2) # Store the resultant subsequence rs = [] # Function to calculate maximum # number from nums of length c_len def helper(nums, c_len): # Store the resultant maximum ans = [] # Length of the nums array ln = len(nums) # Traverse the nums array for idx, val in enumerate(nums): while ans and ans[-1] < val and ln-idx > c_len-len(ans): # If true, then pop # out the last element ans.pop(-1) # Check the length with # required length if len(ans) < c_len: # Append the value to ans ans.append(val) # Return the ans return ans # Traverse and pick the maximum for s1 in range(max(0, k-l2), min(k, l1)+1): # p1 and p2 stores maximum number possible # of length s1 and k - s1 from # the arrays nums1[] & nums2[] p1, p2 = helper(nums1, s1), helper(nums2, k-s1) # Update the maximum number rs = max(rs, [max(p1, p2).pop(0) for _ in range(k)]) # Return the result return rs # Driver Codearr1 = [3, 4, 6, 5]arr2 = [9, 1, 2, 5, 8, 3]K = 5# Function Callprint(maxNumber(arr1, arr2, K)) |
C#
// C# code for the above approachusing System;using System.Collections.Generic;class GFG { // Function to calculate maximum // number from nums of length c_len static List<int> Helper(List<int> nums, int c_len) { // Store the resultant maximum List<int> ans = new List<int>(); // Length of the nums array int ln = nums.Count; // Traverse the nums array for (int i = 0; i < ln; i++) { while (ans.Count > 0 && ans[ans.Count - 1] < nums[i] && ((ln - i) > (c_len - ans.Count))) { // If true, then pop out the last element ans.RemoveAt(ans.Count - 1); } // Check the length with required length if (ans.Count < c_len) { // Append the value to ans ans.Add(nums[i]); } } // Return the ans return ans; } // Returns True if a1 is greater than a2 static bool Comp(List<int> a1, List<int> a2) { int s1 = a1.Count; int s2 = a2.Count; int i1 = 0, i2 = 0; while (i1 < s1 && i2 < s2) { if (a1[i1] > a2[i2]) { return true; } else if (a1[i1] < a2[i2]) { return false; } i1++; i2++; } if (i1 < s1) return true; return false; } // Function to find maximum K-digit number // possible from subsequences of the // two arrays nums1[] and nums2[] static List<int> MaxNumber(List<int> nums1, List<int> nums2, int k) { // Store lengths of the arrays int l1 = nums1.Count; int l2 = nums2.Count; // Store the resultant subsequence List<int> rs = new List<int>(); // Traverse and pick the maximum for (int s1 = Math.Max(0, k - l2); s1 <= Math.Min(k, l1); s1++) { // p1 and p2 stores maximum number possible // of length s1 and k - s1 from // the arrays nums1[] & nums2[] List<int> p1 = new List<int>(); List<int> p2 = new List<int>(); p1 = Helper(nums1, s1); p2 = Helper(nums2, k - s1); // Update the maximum number List<int> temp = new List<int>(); for (int j = 0; j < k; j++) { List<int> temp2 = Comp(p1, p2) ? p1 : p2; int fr = temp2[0]; if (Comp(p1, p2)) { if (p1.Count > 0) { p1.RemoveAt(0); } } else { if (p2.Count > 0) { p2.RemoveAt(0); } } temp.Add(fr); } rs = Comp(rs, temp) ? rs : temp; } // Return the result return rs; } public static void Main(string[] args) { List<int> arr1 = new List<int>{ 3, 4, 6, 5 }; List<int> arr2 = new List<int>{ 9, 1, 2, 5, 8, 3 }; int k = 5; List<int> result = MaxNumber(arr1, arr2, k); foreach(int i in result) { Console.Write(i + " "); } }}// This code is contributed by lokeshpotta20. |
Javascript
<script>// javascript program for the above approachclass GFG{ // Function to calculate maximum // number from nums of length c_len static helper(nums, c_len) { // Store the resultant maximum var ans = new Array(); // Length of the nums array var ln = nums.length; // Traverse the nums array for (let i=0; i < ln; i++) { while (ans.length > 0 && ans[ans.length - 1] < nums[i] && ((ln - i) > (c_len - ans.length))) { // If true, then pop // out the last element ans.splice(ans.length - 1,1); } // Check the length with // required length if (ans.length < c_len) { // Append the value to ans (ans.push(nums[i]) > 0); } } // Return the ans return ans; } // Returns True if a1 is greater than a2 static comp(a1, a2) { var s1 = a1.length; var s2 = a2.length; var i1 = 0; var i2 = 0; while (i1 < s1 && i2 < s2) { if (a1[i1] > a2[i2]) { return true; } else if (a1[i1] < a2[i2]) { return false; } i1++; i2++; } if (i1 < s1) { return true; } return false; } // Function to find maximum K-digit number // possible from subsequences of the // two arrays nums1[] and nums2[] static maxNumber(nums1, nums2, k) { // Store lengths of the arrays var l1 = nums1.length; var l2 = nums2.length; // Store the resultant subsequence var rs = new Array(); // Traverse and pick the maximum for (let s1=Math.max(0, k-l2); s1 <= Math.min(k,l1); s1++) { // p1 and p2 stores maximum number possible // of length s1 and k - s1 from // the arrays nums1[] & nums2[] var p1 = new Array(); var p2 = new Array(); p1 = GFG.helper(nums1, s1); p2 = GFG.helper(nums2, k - s1); // Update the maximum number var temp = new Array(); for (let j=0; j < k; j++) { var temp2 = GFG.comp(p1, p2) ? p1 : p2; var fr = temp2[0]; if (GFG.comp(p1, p2)) { if (p1.length > 0) { p1.splice(0,1); } } else { if (p2.length > 0) { p2.splice(0,1); } } (temp.push(fr) > 0); } rs = GFG.comp(rs, temp) ? rs : temp; } // Return the result return rs; } static main(args) { var arr1 = [3,6,4,5]; var arr2 = [9,1,2,5,8,3]; var K = 5; // Function Call var v = GFG.maxNumber(arr1, arr2, K); for (let i=0; i < v.length; i++) { document.write(v[i] + " "); } }}GFG.main([]);</script> |
Output:
[9, 8, 6, 5, 3]
Time Complexity: O(K*(M + N))
Auxiliary Space: O(K)
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!
