Check if mapping is possible to make sum of first array larger than second array
Given a positive integer K and two arrays A[] and B[] of size N and M respectively, each containing elements in the range [1, K]. The task is to map all numbers from 1 to K with a function f, such that f(1)<f(2)<f(3)<…<f(K), and find whether the sum of f(A[i]) for 0≤i<N is greater than the sum of f(B[i]) for 0≤i<M.
Examples:
Input: A[] = {2, 2, 2}, B[] = {1, 1, 3}, K=3
Output: YES
Explanation: One possible way is to assign the following values to the function f as follows:
f(1)=1
f(2)=2
f(3)=3
Sum of f(A[i]) for every i = 2+2+2 = 6 and sum of f(B[i]) for every i = 1+1+3 = 5.Input: A[] = {8, 2, 8, 6, 9, 10}, B[] = {1, 2, 3, 4}, K=10
Output: YES
Approach: Follow the steps below to solve the problem:
- If the value of N>M, the print “YES” as the answer, since an assignment can always be made such that the sum of A is greater than B.
- Otherwise, sort the arrays A[] and B[] in descending order.
- Iterate in the range [0, N-1], using the variable i and if for any index, A[i]>B[i], print “YES” as the answer since assigning a large enough value to A[i] will make the sum of A[] is greater than B[].
- Otherwise, print “NO” 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 check if mapping is // possible to make sum of first array // larger than second array int isPossible( int A[], int B[], int K, int N, int M) { // If N > M, an assignment is // always possible if (N > M) return 1; // Sort A[] in descending order sort(A, A + N, greater< int >()); // Sort B[] in descending order sort(B, B + M, greater< int >()); // Traverse in the arrays for ( int i = 0; i < N; i++) // If A[i] > B[i], assignment // is possible if (A[i] > B[i]) return 1; return 0; } // Driver Code int main() { // Given Input int A[] = { 2, 2, 2 }; int B[] = { 1, 1, 3 }; int K = 3; int N = sizeof (A) / sizeof (A[0]); int M = sizeof (B) / sizeof (B[0]); // Function Call if (isPossible(A, B, K, N, M)) cout << "YES" ; else cout << "NO" ; return 0; } |
Java
// Java Program for the above approach import java.io.*; import java.util.Arrays; import java.util.Collections; class GFG { public static void reverse( int array[]) { // Length of the array int n = array.length; // Swapping the first half elements with last half // elements for ( int i = 0 ; i < n / 2 ; i++) { // Storing the first half elements temporarily int temp = array[i]; // Assigning the first half to the last half array[i] = array[n - i - 1 ]; // Assigning the last half to the first half array[n - i - 1 ] = temp; } } // Function to check if mapping is // possible to make sum of first array // larger than second array public static int isPossible( int A[], int B[], int K, int N, int M) { // If N > M, an assignment is // always possible if (N > M) return 1 ; // Sort A[] in descending order Arrays.sort(A); reverse(A); // Sort B[] in descending order Arrays.sort(B); reverse(B); // Traverse in the arrays for ( int i = 0 ; i < N; i++) // If A[i] > B[i], assignment // is possible if (A[i] > B[i]) return 1 ; return 0 ; } public static void main(String[] args) { int A[] = { 2 , 2 , 2 }; int B[] = { 1 , 1 , 3 }; int K = 3 ; int N = A.length; int M = B.length; // Function Call if (isPossible(A, B, K, N, M) == 1 ) System.out.println( "YES" ); else System.out.println( "NO" ); } } // This code is contributed by lokeshpotta20 |
Python3
# Python3 program for the above approach # Function to check if mapping is # possible to make sum of first array # larger than second array def isPossible(A, B, K, N, M): # If N > M, an assignment is # always possible if (N > M): return 1 # Sort A[] in descending order A.sort(reverse = True ) # Sort B[] in descending order B.sort(reverse = True ) # Traverse in the arrays for i in range (N): # If A[i] > B[i], assignment # is possible if (A[i] > B[i]): return 1 return 0 # Driver Code if __name__ = = '__main__' : # Given Input A = [ 2 , 2 , 2 ] B = [ 1 , 1 , 3 ] K = 3 N = len (A) M = len (B) # Function Call if (isPossible(A, B, K, N, M)): print ( "YES" ) else : print ( "NO" ) # This code is contributed by SURENDRA_GANGWAR |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to check if mapping is // possible to make sum of first array // larger than second array static int isPossible( int []A, int []B, int K, int N, int M) { // If N > M, an assignment is // always possible if (N > M) return 1; // Sort A[] in descending order Array.Sort(A); Array.Reverse(A); // Sort B[] in descending order Array.Sort(B); Array.Reverse(B); // Traverse in the arrays for ( int i = 0; i < N; i++) // If A[i] > B[i], assignment // is possible if (A[i] > B[i]) return 1; return 0; } // Driver Code public static void Main() { // Given Input int []A = { 2, 2, 2 }; int []B = { 1, 1, 3 }; int K = 3; int N = A.Length; int M = B.Length; // Function Call if (isPossible(A, B, K, N, M) == 1) Console.Write( "YES" ); else Console.Write( "NO" ); } } // This code is contributed by ipg2016107 |
Javascript
<script> // JavaScript program for the above approach // Function to check if mapping is // possible to make sum of first array // larger than second array function isPossible(A, B, K, N, M) { // If N > M, an assignment is // always possible if (N > M) return 1; // Sort A[] in descending order A.sort( function (a,b) { return b - a }) // Sort B[] in descending order B.sort( function (a,b) { return b - a }) // Traverse in the arrays for (let i = 0; i < N; i++) // If A[i] > B[i], assignment // is possible if (A[i] > B[i]) return 1; return 0; } // Driver Code // Given Input var A = [2, 2, 2]; var B = [1, 1, 3]; var K = 3; var N = A.length; var M = B.length; // Function Call if (isPossible(A, B, K, N, M)) document.write( "YES" ); else document.write( "NO" ); </script> |
YES
Time Complexity: O(N*log(N))
Auxiliary Space: O(1)
Contact Us