Given an array arr[] consisting of N positive integers and a positive integer M, the task is to find the smallest possible integer K such that ceil(arr[0]/K) + ceil(arr[1]/K) +….+ ceil(arr[N – 1]/K) is at most M.
Examples:
Input: arr[] = {4, 3, 2, 7}, M = 5
Output: 4
Explanation:
For K = 4, the value of ceil(4/4) + ceil(3/4) + ceil(2/4) + ceil(7/4) = 1 + 1 + 1 + 2 = 5. Therefore, print 5.Input: arr[] = {1, 2, 3}, M = 4
Output: 2
Approach: The idea is to use the Binary Search. Set the low value as 1 and high value as a maximum value from the array arr[] and find the K value which is less than or equal to M by applying binary search. Follow the steps below to solve the problem:
- Initialize variables, say low = 1 and high as the maximum array element.
- Iterate over a while loop till high – low > 1 and perform the following tasks:
- Update the value of mid by mid = (low + high)/2.
- Traverse the array arr[] and find the sum of ceil(arr[i]/K) by assuming mid as K.
- If the sum is greater than M, then update the value of high to high = mid. Otherwise, update the value of low to low = mid + 1.
- After completing the above steps, print the value of low if the sum is at most M. Otherwise, print the value of high.
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 the sum of ceil// values of the arr[] for the K value// is at most M or notbool isvalid(int arr[], int K, int N, int M){ // Stores the sum of ceil values int sum = 0; for (int i = 0; i < N; i++) { // Update the sum sum += (int)ceil(arr[i] * 1.0 / K); } // Return true if sum is less than // or equal to M, false otherwise return sum <= M;}// Function to find the smallest possible// integer K such that ceil(arr[0]/K) +// ceil(arr[1]/K) +....+ ceil(arr[N-1]/K)// is less than or equal to Mint smallestValueForK(int arr[], int N, int M){ // Stores the low value int low = 1; // Stores the high value int high = *max_element(arr, arr + N); // Stores the middle value int mid; while (high - low > 1) { // Update the mid value mid = (high + low) / 2; // Check if the mid value is K if (!isvalid(arr, mid, N, M)) // Update the low value low = mid + 1; else // Update the high value high = mid; } // Check if low is K or high is K // and return it return isvalid(arr, low, N, M) ? low : high;}// Driver Codeint main(){ int arr[] = { 4, 3, 2, 7 }; int N = sizeof(arr) / sizeof(arr[0]); int M = 5; cout << smallestValueForK(arr, N, M); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to check if the sum of ceil // values of the arr[] for the K value // is at most M or not static boolean isvalid(int[] arr, int K, int N, int M) { // Stores the sum of ceil values int sum = 0; for (int i = 0; i < N; i++) { // Update the sum sum += Math.ceil(arr[i] * 1.0 / K); } // Return true if sum is less than // or equal to M, false otherwise return sum <= M; } // Function to find the smallest possible // integer K such that ceil(arr[0]/K) + // ceil(arr[1]/K) +....+ ceil(arr[N-1]/K) // is less than or equal to M static int smallestValueForK(int[] arr, int N, int M) { // Stores the low value int low = 1; // Stores the high value int high = arr[0]; //Loop through the array for (int i = 0; i < arr.length; i++) { //Compare elements of array with max if(arr[i] > high) high = arr[i]; } // Stores the middle value int mid; while (high - low > 1) { // Update the mid value mid = (high + low) / 2; // Check if the mid value is K if (isvalid(arr, mid, N, M)==false) // Update the low value low = mid + 1; else // Update the high value high = mid; } // Check if low is K or high is K // and return it return isvalid(arr, low, N, M) ? low : high; } // Driver Code public static void main(String args[]) { int arr[] = { 4, 3, 2, 7 }; int N = arr.length; int M = 5; System.out.print(smallestValueForK(arr, N, M)); }}// This code is contributed by SURENDRA_GANGWAR. |
Python3
# python program for the above approachimport math# Function to check if the sum of ceil# values of the arr[] for the K value# is at most M or notdef isvalid(arr, K, N, M): # Stores the sum of ceil values sum = 0 for i in range(0, N): # Update the sum sum += math.ceil(arr[i] * 1.0 / K) # Return true if sum is less than # or equal to M, false otherwise return sum <= M# Function to find the smallest possible# integer K such that ceil(arr[0]/K) +# ceil(arr[1]/K) +....+ ceil(arr[N-1]/K)# is less than or equal to Mdef smallestValueForK(arr, N, M): # Stores the low value low = 1 # Stores the high value high = arr[0] for i in range(1, len(arr)): high = max(high, arr[i]) # Stores the middle value mid = 0 while (high - low > 1): # Update the mid value mid = (high + low) // 2 # Check if the mid value is K if (not isvalid(arr, mid, N, M)): # Update the low value low = mid + 1 else: # Update the high value high = mid # Check if low is K or high is K # and return it if(isvalid(arr, low, N, M)): return low else: return high# Driver Codeif __name__ == "__main__": arr = [4, 3, 2, 7] N = len(arr) M = 5 print(smallestValueForK(arr, N, M)) # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;using System.Linq;class GFG { // Function to check if the sum of ceil // values of the arr[] for the K value // is at most M or not static bool isvalid(int[] arr, int K, int N, int M) { // Stores the sum of ceil values int sum = 0; for (int i = 0; i < N; i++) { // Update the sum sum += (int)Math.Ceiling(arr[i] * 1.0 / K); } // Return true if sum is less than // or equal to M, false otherwise return sum <= M; } // Function to find the smallest possible // integer K such that ceil(arr[0]/K) + // ceil(arr[1]/K) +....+ ceil(arr[N-1]/K) // is less than or equal to M static int smallestValueForK(int[] arr, int N, int M) { // Stores the low value int low = 1; // Stores the high value int high = arr.Max(); // Stores the middle value int mid; while (high - low > 1) { // Update the mid value mid = (high + low) / 2; // Check if the mid value is K if (!isvalid(arr, mid, N, M)) // Update the low value low = mid + 1; else // Update the high value high = mid; } // Check if low is K or high is K // and return it return isvalid(arr, low, N, M) ? low : high; } // Driver Code public static void Main() { int[] arr = { 4, 3, 2, 7 }; int N = arr.Length; int M = 5; Console.WriteLine(smallestValueForK(arr, N, M)); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to check if the sum of ceil // values of the arr[] for the K value // is at most M or not function isvalid(arr, K, N, M) { // Stores the sum of ceil values let sum = 0; for (let i = 0; i < N; i++) { // Update the sum sum += Math.ceil(arr[i] * 1.0 / K); } // Return true if sum is less than // or equal to M, false otherwise return sum <= M; } // Function to find the smallest possible // integer K such that ceil(arr[0]/K) + // ceil(arr[1]/K) +....+ ceil(arr[N-1]/K) // is less than or equal to M function smallestValueForK(arr, N, M) { // Stores the low value let low = 1; // Stores the high value let high = Number.MIN_VALUE; for (let i = 0; i < N; i++) { high = Math.max(high, arr[i]); } // Stores the middle value let mid; while (high - low > 1) { // Update the mid value mid = (high + low) / 2; // Check if the mid value is K if (!isvalid(arr, mid, N, M)) // Update the low value low = mid + 1; else // Update the high value high = mid; } // Check if low is K or high is K // and return it return isvalid(arr, low, N, M) ? low : high; } // Driver Code let arr = [4, 3, 2, 7]; let N = arr.length; let M = 5; document.write(smallestValueForK(arr, N, M)); // This code is contributed by Potta Lokesh </script> |
Output:
4
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
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!
Share your thoughts in the comments
