In the Create Maximum Number problem, we have given two arrays of length n and m with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from the digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits.
Table of Contents
Input format
The first line contains two integers n, m, k — the size of the first array, size of the second array, and the size of the required array.
The second line contains n integers, ith of them denotes nums1i
The last line contains m integers, ith of them denotes nums2i
Output format
Print the maximum number of length k <= m + n from digits of the two given array. The relative order of the digits from the same array must be preserved.
Input 4 6 5 3 4 6 5 9 1 2 5 8 3 Output 9 8 6 5 3
Algorithm for Create Maximum Number
- For every valid length i
- Create a maximum number of the size I from 1st array, the maximum number of size k-I from the second array.
- Create the maximum number of two arrays using all of their digits
- Take the maximum of all these numbers
- Print the final array.
Function to find lexicographically larger of two arrays
In this function, we have two array nums1, nums2 and two index i, j. We return true if nums2 is lexicographically greater than nums1 when comparing from the ith index of nums1 and jth index of nums2 else false.
Algorithm
- The two variables I and j points to nums1i and nums2j
- Increment I and j till I and j are in range and nums1i is equal to nums2j.
- If j is out of range of nums1 is greater than nums2j than return true else return false.
bool Greater(vector<int> &nums1, int i, vector<int> &nums2, int j)
{
while (i < nums1.size() && j < nums2.size() && nums1[i] == nums2[j])
{
++i;
++j;
}
if (j == nums2.size())
return true;
if (i < nums1.size() && nums1[i] > nums2[j])
return true;
return false;
}
Function to create a maximum array of size k by merging two arrays
Algorithm
- Initialize an array “ans” of size k.
- Initialize two variables i=0 and j=0 which points to the nums1i and num2j.
- For x in range 0 to k-1
- Check if Greater(nums1,I,nums2,j) is true (which means nums1 is lexicographically greater than nums2 when compared from ith and jth index of the arrays respectively) then assign ans[x]=nums1[i], and increment I by 1.
- If Greater(nums1,I,nums2,j) is false, then assign ans[x]=nums2[j], and increment j by 1.
- Return ans array.
vector<int> merge(vector<int> &nums1, vector<int> &nums2, int k)
{
vector<int> res(k, 0);
for (int i = 0, j = 0, r = 0; r < k; ++r)
{
res[r] = Greater(nums1, i, nums2, j) ? nums1[i++] : nums2[j++];
}
return res;
}
Implementation
C++ program for Create Maximum Number
#include <bits/stdc++.h>
using namespace std;
bool Greater(vector<int> &nums1, int i, vector<int> &nums2, int j)
{
while (i < nums1.size() && j < nums2.size() && nums1[i] == nums2[j])
{
++i;
++j;
}
if (j == nums2.size())
return true;
if (i < nums1.size() && nums1[i] > nums2[j])
return true;
return false;
}
vector<int> biggestNumber(vector<int> &nums, int k)
{
int n = nums.size();
vector<int> ans(k);
for (int i = 0, j = 0; i < n; ++i)
{
while (n - i + j > k && j > 0 && ans[j - 1] < nums[i])
j--;
if (j < k)
ans[j++] = nums[i];
}
return ans;
}
vector<int> merge(vector<int> &nums1, vector<int> &nums2, int k)
{
vector<int> res(k, 0);
for (int i = 0, j = 0, r = 0; r < k; ++r)
{
res[r] = Greater(nums1, i, nums2, j) ? nums1[i++] : nums2[j++];
}
return res;
}
void maxNumber(vector<int> &nums1, vector<int> &nums2, int k)
{
int n = nums1.size();
int m = nums2.size();
vector<int> ans(k, -1);
for (int i = max(0, k - m); i <= min(k, n); i++)
{
vector<int> a = biggestNumber(nums1, i);
vector<int> b = biggestNumber(nums2, k - i);
ans = max(ans, merge(a, b, k));
}
for (int i = 0; i < k; i++)
{
cout << ans[i] << " ";
}
cout << endl;
return;
}
int main()
{
int n, m, k;
cin >> n >> m >> k;
vector<int> nums1(n), nums2(m);
for (int i = 0; i < n; i++)
{
cin >> nums1[i];
}
for (int i = 0; i < m; i++)
{
cin >> nums2[i];
}
maxNumber(nums1, nums2, k);
return 0;
}
4 6 5 3 4 6 5 9 1 2 5 8 3
9 8 6 5 3
JAVA program for Create Maximum Number
import java.util.*;
public class Main
{
//function to construct the maximum array from the given arrays
public static int[] maxNumber(int[] nums1, int[] nums2, int k) {
int n = nums1.length;
int m = nums2.length;
int[] ans = new int[k];
for (int i = Math.max(0, k - m); i <= k && i <= n; ++i) {
int[] candidate = merge(maxArray(nums1, i), maxArray(nums2, k - i), k);
if (greater(candidate, 0, ans, 0)) ans = candidate;
}
return ans;
}
//function to merge two arrays
public static int[] merge(int[] nums1, int[] nums2, int k) {
int[] ans = new int[k];
for (int i = 0, j = 0, r = 0; r < k; ++r)
ans[r] = greater(nums1, i, nums2, j) ? nums1[i++] : nums2[j++];
return ans;
}
//function to find the greater array
public static boolean greater(int[] nums1, int i, int[] nums2, int j) {
while (i < nums1.length && j < nums2.length && nums1[i] == nums2[j]) {
i++;
j++;
}
return j == nums2.length || (i < nums1.length && nums1[i] > nums2[j]);
}
//function to make the greatest array of size k
public static int[] maxArray(int[] nums, int k) {
int n = nums.length;
int[] ans = new int[k];
for (int i = 0, j = 0; i < n; ++i) {
while (n - i + j > k && j > 0 && ans[j - 1] < nums[i]) j--;
if (j < k) ans[j++] = nums[i];
}
return ans;
}
public static void main(String[] args) {
Scanner sc = new Scanner( System.in ) ;
int n=sc.nextInt();
int m=sc.nextInt();
int k=sc.nextInt();
int[] nums1 = new int[n];
int[] nums2 = new int[m];
for(int i=0;i<n;i++){
nums1[i]=sc.nextInt();
}
for(int i=0;i<m;i++){
nums2[i]=sc.nextInt();
}
int[] ans=maxNumber(nums1,nums2,k);
for(int i=0;i<ans.length;i++){
System.out.print(ans[i]+" ");
}
}
}
2 3 5 6 7 6 0 4
6 7 6 0 4
Complexity Analysis
Time complexity
For every length, we find the maximum number of the size I from the array which in worst case takes O(i^2) time so overall time complexity is O((m+n)^3).
Space complexity
Space complexity is O(K) because we only take the “ans” array.