Given a positive integer M and two arrays arr[] and value[] of N and K positive integers respectively, the task is to add every element in value[] to an element in arr[] such that after all the additions are performed, the maximum element in the array is at most M. If it is possible to do so, then print “Yes”. Otherwise, print “No”.
Examples:
Input: arr[] = {5, 9, 3, 8, 7}, value[] = {1, 2, 3, 4}, M = 9
Output: Yes
Explanation:
Add 1 & 3 to arr[0] maximizing it to 9.
Add 2 & 4 to arr[2] maximizes it to 9.
Hence, the final arr becomes {9, 9, 9, 8, 7}.
Input: arr[] = {5, 8, 3, 8, 7}, value[] = {1, 2, 3, 4}, M = 8
Output: No
Explanation:
Adding 1 to arr[4], 3 to arr[0] and 4 to arr[2], the array is modified to {8, 8, 7, 8, 8}.
The current maximum element in arr[] is 8.
Hence, only 2 needs to be added from value[] to any element of arr[].
But, on adding 2 to any element in arr[], the maximum element in the array exceeds 8.
Naive Approach:
The simplest approach is to choose any K elements from the given array arr[] and add the K values in the value[] array with these K values chosen. These K values can be added to the K chosen numbers of the array arr[] in K! ways (in the worst case).
Time Complexity: O( NPK )
Efficient Approach:
Follow the steps below to solve the problem:
- Sort the elements in value[] array in decreasing order.
- Store all the elements of arr[] in the min priority queue.
- Now extract the minimum element(say X) from the priority queue and add the elements from the array value[] to X.
- While adding value from the array value[] to X exceeds M, then insert the element X into priority queue and repeat the above step for the next minimum value in the priority queue.
- If all the elements in value[] are added to some elements in arr[] then “Yes”, else print “No”.
Below is the implementation of the above approach:
C++
// C++ Program to implement the // above approach #include <bits/stdc++.h> using namespace std; // Function which checks if all // additions are possible void solve(int ar[], int values[], int N, int K, int M) { // Sorting values[] in // decreasing order sort(values, values + K, greater<int>()); // Minimum priority queue which // contains all the elements // of array arr[] priority_queue<int, vector<int>, greater<int> > pq; for (int x = 0; x < N; x++) { pq.push(ar[x]); } // poss stores whether all the // additions are possible bool poss = true; for (int x = 0; x < K; x++) { // Minimum value in the // priority queue int mini = pq.top(); pq.pop(); int val = mini + values[x]; // If on addition it exceeds // M then not possible if (val > M) { poss = false; break; } pq.push(val); } // If all elements are added if (poss) { cout << "Yes" << endl; } else { cout << "No" << endl; } } // Driver Code int main() { int ar[] = { 5, 9, 3, 8, 7 }; int N = 5; int values[] = { 1, 2, 3, 4 }; int K = 4; int M = 9; solve(ar, values, N, K, M); return 0; } |
Java
// Java program to implement the // above approach import java.io.*;import java.util.*; class GFG{ // Function which checks if all // additions are possible static void solve(Integer ar[], Integer values[], int N, int K, int M) { // Sorting values[] in // decreasing order Arrays.sort(values, (a, b) -> b - a); // Minimum priority queue which // contains all the elements // of array arr[] PriorityQueue<Integer> pq = new PriorityQueue<>(); for(int x = 0; x < N; x++) { pq.add(ar[x]); } // poss stores whether all the // additions are possible boolean poss = true; for(int x = 0; x < K; x++) { // Minimum value in the // priority queue int mini = pq.peek(); pq.poll(); int val = mini + values[x]; // If on addition it exceeds // M then not possible if (val > M) { poss = false; break; } pq.add(val); } // If all elements are added if (poss) { System.out.println("Yes"); } else { System.out.println("No"); } } // Driver Code public static void main(String args[]){ Integer ar[] = { 5, 9, 3, 8, 7 }; int N = 5; Integer values[] = { 1, 2, 3, 4 }; int K = 4; int M = 9; solve(ar, values, N, K, M); } } // This code is contributed by offbeat |
Python3
# Python3 program to implement the # above approach from queue import PriorityQueue # Function which checks if all # additions are possible def solve(ar, values, N, K, M): # Sorting values[] in # decreasing order values.sort(reverse = True) # Minimum priority queue which # contains all the elements # of array arr[] pq = PriorityQueue() for x in range(N): pq.put(ar[x]); # poss stores whether all the # additions are possible poss = True; for x in range(K): # Minimum value in the # priority queue mini = pq.get(); val = mini + values[x]; # If on addition it exceeds # M then not possible if (val > M): poss = False; break; pq.put(val); # If all elements are added if (poss): print("Yes"); else: print("No"); # Driver Code if __name__=='__main__': ar = [ 5, 9, 3, 8, 7 ] N = 5; values = [ 1, 2, 3, 4 ] K = 4; M = 9; solve(ar, values, N, K, M); # This code is contributed by rutvik_56 |
C#
// C# Program to implement the // above approach using System;using System.Collections.Generic;class GFG{ // Function which checks if all // additions are possible static void solve(int[] ar, int[] values, int N, int K, int M) { // Sorting values[] in // decreasing order Array.Sort(values); Array.Reverse(values); // Minimum priority queue which // contains all the elements // of array arr[] List<int> pq = new List<int>(); for (int x = 0; x < N; x++) { pq.Add(ar[x]); } pq.Sort(); // poss stores whether all the // additions are possible bool poss = true; for (int x = 0; x < K; x++) { // Minimum value in the // priority queue int mini = pq[0]; pq.RemoveAt(0); int val = mini + values[x]; // If on addition it exceeds // M then not possible if (val > M) { poss = false; break; } pq.Add(val); pq.Sort(); } // If all elements are added if (poss) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } } // Driver code static void Main() { int[] ar = { 5, 9, 3, 8, 7 }; int N = 5; int[] values = { 1, 2, 3, 4 }; int K = 4; int M = 9; solve(ar, values, N, K, M); }}// This code is contributed by divyeshrabadiya07. |
Javascript
<script>// JavaScript Program to implement the// above approach // Function which checks if all // additions are possible function solve(ar, values, N, K, M) { // Sorting values[] in // decreasing order values.sort((a, b) => a - b); values.reverse(); // Minimum priority queue which // contains all the elements // of array arr[] let pq = new Array(); for (let x = 0; x < N; x++) { pq.push(ar[x]); } pq.sort((a, b) => a -b); // poss stores whether all the // additions are possible let poss = true; for (let x = 0; x < K; x++) { // Minimum value in the // priority queue let mini = pq[0]; pq.shift(); let val = mini + values[x]; // If on addition it exceeds // M then not possible if (val > M) { poss = false; break; } pq.push(val); pq.sort((a, b) => a - b); } // If all elements are added if (poss) { document.write("Yes"); } else { document.write("No"); } }// Driver code let ar = [ 5, 9, 3, 8, 7 ]; let N = 5; let values = [ 1, 2, 3, 4 ]; let K = 4; let M = 9; solve(ar, values, N, K, M);// This code is contributed by gfgking</script> |
Output:
Yes
Time Complexity: O((N+K)*log(N))
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!
