Given two arrays A[] and B[] of size N and M respectively, where each element is in the range [0, 9], the task is to make each element of the array A[] strictly greater than or smaller than every element in the array B[] by changing any element from either array to any number in the range [0, 9], minimum number of times.
Examples:
Input: A[] = [0, 1, 0], B[] = [2, 0, 0]
Output: 2
Explanation:
Modifying the array B[] to [2, 2, 2] makes every element in the array A[] strictly less than every element in the array B[].
Hence, the minimum number of changes required = 2.Input: A[] = [0, 0, 1, 3, 3], B[] = [0, 2, 3]
Output: 3
Explanation:
Modifying the array B[] to [4, 4, 4] makes every element in the array A[] strictly less than every element in the array B[].
Hence, the minimum number of changes required = 3.
Approach: The idea to solve the given problem is to use two auxiliary arrays prefix_a[] and prefix_b[] of size 10, where prefix_a[i] and prefix_b[i] stores the number of elements in the array A[] ≤ i and the number of elements in the array B[] ≤ i respectively. Follow the steps below to solve the problem:
- Initialize two arrays, prefix_a[] and prefix_b[] of size 10 with {0}.
- Store the frequencies of every element in the arrays A[] and B[] in arrays prefix_a, and prefix_b respectively.
- Perform the prefix sum on the array prefix_a by iterating in the range [1, 9] using the variable i and update prefix_a[i] as (prefix[i] + prefix_a[i – 1]).
- Repeat the above step for the array prefix_b[].
- Iterate in the range [0, 9] using the variable i
- Store the number of operations to make every element in the array A[] strictly greater than the digit i and make every element in the array B[] less than digit i in a variable, say X.
- Initialize it with prefix_a[i] + M – prefix_b[i].
- Similarly, store the number of operations to make every element in the array B[] strictly greater than digit i and make every element in the array A[] less than digit i in a variable, say Y.
- Initialize it with prefix_b[i] + N – prefix_a[i].
- Update the overall minimum number of operations as the minimum of X and Y. Store the minimum obtained in a variable, say ans.
- After completing the above steps, print the value of ans as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimize// replacements to make every element// in the array A[] strictly greater// than every element in B[] or vice-versavoid MinTime(int* a, int* b, int n, int m){ // Store the final result int ans = INT_MAX; // Create two arrays and // initialize with 0s int prefix_a[10] = { 0 }; int prefix_b[10] = { 0 }; // Traverse the array a[] for (int i = 0; i < n; i++) { // Increment prefix_a[a[i]] by 1 prefix_a[a[i]]++; } // Traverse the array b[] for (int i = 0; i < m; i++) { // Increment prefix_b[b[i]] by 1 prefix_b[b[i]]++; } // Calculate prefix sum // of the array a[] for (int i = 1; i <= 9; i++) { prefix_a[i] += prefix_a[i - 1]; } // Calculate prefix sum // of the array b[] for (int i = 1; i <= 9; i++) { prefix_b[i] += prefix_b[i - 1]; } // Iterate over the range [0, 9] for (int i = 0; i <= 9; i++) { // Make every element in array // a[] strictly greater than digit // i and make every element in the // array b[] less than digit i ans = min(ans, prefix_a[i] + m - prefix_b[i]); // Make every element in array // b[] strictly greater than digit // i and make every element in // array a[] less than digit i ans = min(ans, n - prefix_a[i] + prefix_b[i]); } // Print the answer cout << ans;}// Driver Codeint main(){ int A[] = { 0, 0, 1, 3, 3 }; int B[] = { 2, 0, 3 }; int N = sizeof(A) / sizeof(A[0]); int M = sizeof(B) / sizeof(B[0]); MinTime(A, B, N, M); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to find the minimize// replacements to make every element// in the array A[] strictly greater// than every element in B[] or vice-versastatic void MinTime(int []a, int []b, int n, int m){ // Store the final result int ans = 2147483647; // Create two arrays and // initialize with 0s int []prefix_a = new int[10]; int []prefix_b = new int[10]; // Traverse the array a[] for (int i = 0; i < n; i++) { // Increment prefix_a[a[i]] by 1 prefix_a[a[i]]++; } // Traverse the array b[] for (int i = 0; i < m; i++) { // Increment prefix_b[b[i]] by 1 prefix_b[b[i]]++; } // Calculate prefix sum // of the array a[] for (int i = 1; i <= 9; i++) { prefix_a[i] += prefix_a[i - 1]; } // Calculate prefix sum // of the array b[] for (int i = 1; i <= 9; i++) { prefix_b[i] += prefix_b[i - 1]; } // Iterate over the range [0, 9] for (int i = 0; i <= 9; i++) { // Make every element in array // a[] strictly greater than digit // i and make every element in the // array b[] less than digit i ans = Math.min(ans, prefix_a[i] + m - prefix_b[i]); // Make every element in array // b[] strictly greater than digit // i and make every element in // array a[] less than digit i ans = Math.min(ans, n - prefix_a[i] + prefix_b[i]); } // Print the answer System.out.println(ans);}// Driver Codepublic static void main(String [] args){ int []A = { 0, 0, 1, 3, 3 }; int []B = { 2, 0, 3 }; int N = A.length; int M = B.length; MinTime(A, B, N, M);}}// This code is contributed by chitranayal. |
Python3
# Python program for the above approach# Function to find the minimize# replacements to make every element# in the array A[] strictly greater# than every element in B[] or vice-versadef MinTime(a, b, n, m): # Store the final result ans = float('inf') # Create two arrays and # initialize with 0s prefix_a = [ 0 ]*10 prefix_b = [ 0 ]*10 # Traverse the array a[] for i in range(n): # Increment prefix_a[a[i]] by 1 prefix_a[a[i]] += 1 # Traverse the array b[] for i in range(m): # Increment prefix_b[b[i]] by 1 prefix_b[b[i]] += 1 # Calculate prefix sum # of the array a[] for i in range(1, 10): prefix_a[i] += prefix_a[i - 1] # Calculate prefix sum # of the array b[] for i in range(1, 10): prefix_b[i] += prefix_b[i - 1] # Iterate over the range [0, 9] for i in range(1, 10): # Make every element in array # a[] strictly greater than digit # i and make every element in the # array b[] less than digit i ans = min(ans, prefix_a[i] + m- prefix_b[i]) # Make every element in array # b[] strictly greater than digit # i and make every element in # array a[] less than digit i ans = min(ans, n - prefix_a[i] + prefix_b[i]) # Print the answer print(ans)# Driver CodeA = [ 0, 0, 1, 3, 3 ]B = [ 2, 0, 3 ]N = len(A)M = len(B)MinTime(A, B, N, M)# This code is contributed by rohitsingh07052. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to find the minimize// replacements to make every element// in the array A[] strictly greater// than every element in B[] or vice-versastatic void MinTime(int []a, int []b, int n, int m){ // Store the final result int ans = 2147483647; // Create two arrays and // initialize with 0s int []prefix_a = new int[10]; int []prefix_b = new int[10]; Array.Clear(prefix_a,0,prefix_a.Length); Array.Clear(prefix_b,0,prefix_b.Length); // Traverse the array a[] for (int i = 0; i < n; i++) { // Increment prefix_a[a[i]] by 1 prefix_a[a[i]]++; } // Traverse the array b[] for (int i = 0; i < m; i++) { // Increment prefix_b[b[i]] by 1 prefix_b[b[i]]++; } // Calculate prefix sum // of the array a[] for (int i = 1; i <= 9; i++) { prefix_a[i] += prefix_a[i - 1]; } // Calculate prefix sum // of the array b[] for (int i = 1; i <= 9; i++) { prefix_b[i] += prefix_b[i - 1]; } // Iterate over the range [0, 9] for (int i = 0; i <= 9; i++) { // Make every element in array // a[] strictly greater than digit // i and make every element in the // array b[] less than digit i ans = Math.Min(ans, prefix_a[i] + m - prefix_b[i]); // Make every element in array // b[] strictly greater than digit // i and make every element in // array a[] less than digit i ans = Math.Min(ans, n - prefix_a[i] + prefix_b[i]); } // Print the answer Console.WriteLine(ans);}// Driver Codepublic static void Main(){ int []A = { 0, 0, 1, 3, 3 }; int []B = { 2, 0, 3 }; int N = A.Length; int M = B.Length; MinTime(A, B, N, M);}}// This code is contributed by bgangwar59. |
Javascript
<script>// Javascript program for the above approach// Function to find the minimize// replacements to make every element// in the array A[] strictly greater// than every element in B[] or vice-versafunction Mletime(a, b, n, m){ // Store the final result let ans = 2147483647; // Create two arrays and // initialize with 0s let prefix_a = []; for (let i = 0; i < 10; i++) { prefix_a[i] = 0; } let prefix_b = []; for (let i = 0; i < 10; i++) { prefix_b[i] = 0; } // Traverse the array a[] for (let i = 0; i < n; i++) { // Increment prefix_a[a[i]] by 1 prefix_a[a[i]]++; } // Traverse the array b[] for (let i = 0; i < m; i++) { // Increment prefix_b[b[i]] by 1 prefix_b[b[i]]++; } // Calculate prefix sum // of the array a[] for (let i = 1; i <= 9; i++) { prefix_a[i] += prefix_a[i - 1]; } // Calculate prefix sum // of the array b[] for (let i = 1; i <= 9; i++) { prefix_b[i] += prefix_b[i - 1]; } // Iterate over the range [0, 9] for (let i = 0; i <= 9; i++) { // Make every element in array // a[] strictly greater than digit // i and make every element in the // array b[] less than digit i ans = Math.min(ans, prefix_a[i] + m - prefix_b[i]); // Make every element in array // b[] strictly greater than digit // i and make every element in // array a[] less than digit i ans = Math.min(ans, n - prefix_a[i] + prefix_b[i]); } // Print the answer document.write(ans);}// Driver Code let A = [ 0, 0, 1, 3, 3 ]; let B = [ 2, 0, 3 ]; let N = A.length; let M = B.length; Mletime(A, B, N, M);</script> |
Output:
3
Time Complexity: O(N + M)
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!
