Given an array arr[] of size N and with integers M, K. You are allowed to perform an operation where you can increase the value of the least element of the array by 1. You are to do this M times. The task is to find the largest possible value for the Kth smallest value among arr[] after M operations.
Examples
Input: M=10, K=4, arr={5,5,5,5,5}.
Output: 7
Explanation: After 5 operations, each element of the array become 6, and similarly after the next 5 operations, each element of the array become 7.Input: M=7, K=2, arr={5,9,3,6,4,3};
Output: 5
Explanation: Can use 5 operations to increase the 3 smallest values to 5. Cannot further improve 2-nd smallest with the remaining 2 operations.Input: M=10,K=4, arr={1,2,3,4,5};
Output: 5
Explanation: Can perform operations to fill all values to 5. The 4-th smallest value is thus 5.
Approach/Intuition:
One way is to use binary search to find the maximum such answer value that can be achieved by distributing M among K values. If the current mid value is feasible, then the value of the mid is stored as our potential answer, and the search is continued in the upper half of that current search range. Otherwise, the search is continued in the lower half of the search range.
Follow the below steps to implement the above approach:
- First, initialize the input array and variables M and K, and call to getVal function, to return us the answer.
- Now, inside the getVal function,
- sort the array.
- initialize the search range from 0 to 1e9.
- for current mid value, check it is valid or not, if it is valid store it as our answer, and change the range to upper half, otherwise if not valid, change the search range to lower half.
Below is the code to implement the above steps:
C++14
// C++ code to implement the above approach.#include <bits/stdc++.h>using namespace std;// check function to validate our selected kth largest// value.bool check(int mid, int M, int K, vector<int>& arr){ vector<int> temp; for (int i = 0; i < arr.size(); i++) { if (arr[i] < mid) { temp.push_back(arr[i]); } } if (temp.size() < K) return 1; for (int i = 0; i < temp.size(); i++) { if (M + temp[i] < mid) return 0; int minVal = min(M, mid - temp[i]); temp[i] += minVal; M -= minVal; } return 1;}// binary search over the range for finding the exact// answer.int getVal(int& M, int& K, vector<int>& arr){ sort(arr.begin(), arr.end()); int lo = 0, hi = 1e9; int ans; while (lo <= hi) { int mid = (lo + hi) / 2; if (check(mid, M, K, arr)) { ans = mid; lo = mid + 1; } else hi = mid - 1; } return ans;}// Driver's codeint main(){ int M = 10, K = 4; vector<int> arr = { 1, 2, 3, 4, 5 }; cout << getVal(M, K, arr); return 0;} |
Java
// C++ code to implement the above approach.import java.util.*;public class Main { // check function to validate our selected kth largest // value. static boolean check(int mid, int M, int K, List<Integer> arr) { List<Integer> temp = new ArrayList<>(); for (int i = 0; i < arr.size(); i++) { if (arr.get(i) < mid) { temp.add(arr.get(i)); } } if (temp.size() < K) return true; for (int i = 0; i < temp.size(); i++) { if (M + temp.get(i) < mid) return false; int minVal = Math.min(M, mid - temp.get(i)); temp.set(i, temp.get(i) + minVal); M -= minVal; } return true; } // binary search over the range for finding the exact // answer. static int getVal(int M, int K, List<Integer> arr) { Collections.sort(arr); int lo = 0, hi = (int)1e9; int ans = 0; while (lo <= hi) { int mid = (lo + hi) / 2; if (check(mid, M, K, arr)) { ans = mid; lo = mid + 1; } else hi = mid - 1; } return ans; } // Driver's code public static void main(String[] args) { int M = 10, K = 4; List<Integer> arr = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5)); System.out.println(getVal(M, K, arr)); }}// This code is contributed by chetan bargal(chetanb13) |
Python3
# Python3 code to implement the above approach.from typing import List# check function to validate our selected kth largest value.def check(mid: int, M: int, K: int, arr: List[int]) -> bool: temp = [] for i in range(len(arr)): if arr[i] < mid: temp.append(arr[i]) if len(temp) < K: return True for i in range(len(temp)): if M + temp[i] < mid: return False minVal = min(M, mid - temp[i]) temp[i] += minVal M -= minVal return True# binary search over the range for finding the exact answer.def getVal(M: int, K: int, arr: List[int]) -> int: arr.sort() lo = 0 hi = 10**9 ans = 0 while lo <= hi: mid = (lo + hi) // 2 if check(mid, M, K, arr): ans = mid lo = mid + 1 else: hi = mid - 1 return ans# Drive codeif __name__ == '__main__': M = 10 K = 4 arr = [1, 2, 3, 4, 5] print(getVal(M, K, arr)) # This Code is contributed by nikhilsainiofficial546 |
C#
using System;using System.Collections.Generic;using System.Linq;class Program { // Check function to validate our selected kth largest // value. static bool Check(int mid, int M, int K, List<int> arr) { List<int> temp = new List<int>(); for (int i = 0; i < arr.Count; i++) { if (arr[i] < mid) { temp.Add(arr[i]); } } if (temp.Count < K) return true; for (int i = 0; i < temp.Count; i++) { if (M + temp[i] < mid) return false; int minVal = Math.Min(M, mid - temp[i]); temp[i] += minVal; M -= minVal; } return true; } // Binary search over the range for finding the exact // answer. static int GetVal(ref int M, ref int K, List<int> arr) { arr.Sort(); int lo = 0, hi = 1000000000; int ans = 0; while (lo <= hi) { int mid = (lo + hi) / 2; if (Check(mid, M, K, arr)) { ans = mid; lo = mid + 1; } else hi = mid - 1; } return ans; }//Driver code static void Main(string[] args) { int M = 10, K = 4; List<int> arr = new List<int>() { 1, 2, 3, 4, 5 }; Console.WriteLine(GetVal(ref M, ref K, arr)); }} |
Javascript
// Javascript code to implement the above approach.// check function to validate our selected kth largest// value.function check(mid, M, K, arr) {let temp = [];for (let i = 0; i < arr.length; i++) { if (arr[i] < mid) { temp.push(arr[i]); }}if (temp.length < K) return true;for (let i = 0; i < temp.length; i++) { if (M + temp[i] < mid) return false; let minVal = Math.min(M, mid - temp[i]); temp[i] += minVal; M -= minVal;}return true;}// binary search over the range for finding the exact// answer.function getVal(M, K, arr) {arr.sort((a, b) => a - b);let lo = 0, hi = 1e9;let ans;while (lo <= hi) { let mid = Math.floor((lo + hi) / 2); if (check(mid, M, K, arr)) { ans = mid; lo = mid + 1; } else hi = mid - 1;}return ans;}// Driver's codelet M = 10, K = 4;let arr = [1, 2, 3, 4, 5];console.log(getVal(M, K, arr));// This code is contributed by Vaibhav Nandan |
5
Time Complexity: O(NlogN), where N is the size of the ‘arr’ vector, as it involves iterating through the entire vector once. The time complexity of the ‘getVal’ function is O(N log N), where N is the size of the ‘arr’ vector, as it involves sorting the ‘arr’ vector and performing a binary search on it.
Auxiliary Space: O(N), as it involves storing the ‘arr’ vector and the ‘temp’ vector inside the ‘check’ function.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
