Smallest Divisor for Sum Constraint in Array Division
Given an array of integers nums and an integer K, the task is to find the smallest positive integer divisor such that, upon dividing all the elements of the given array by it, the sum of the division’s result is less than or equal to the given integer K. Each result of the division is rounded to the nearest integer greater than or equal to that element.
Examples:
Input: A[] = [1, 2, 5, 9], K = 6
Output: 5
Explanation: This is because, if the divisor is 5, the sum will be 5 (1 + 1 + 1 + 2), which is less than 6.Input: A[] = [1, 1, 1, 1], K = 3
Output: 1
Approach: To solve the problem follow the below steps:
- Initialize two variables left to 1 and right to the maximum element in the nums array.
- Perform a binary search within the range [left, right] to find the smallest divisor. Continue the search until left is less than right.
- Inside the binary search loop:
- Calculate the middle value mid as left + (right – left) / 2.
- b. Initialize a variable totalSum to keep track of the total sum of divisions for the current mid value.
- c. Loop through each element in the nums array and for each element num, calculate the division result as (num + mid – 1) / mid. This operation rounds up the division result to the nearest integer greater than or equal to the element.
- d. Add all these division results to totalSum.
- e. Check if totalSum is less than or equal to K. If it is, update right to mid. This means we can potentially find a smaller divisor. If not, update left to mid + 1.
- Once the binary search loop finishes, left will contain the smallest divisor that satisfies the condition. Return left as the result.
Below is the Code for the above approach:
C++
// C++ code for the above approach: #include <algorithm> #include <iostream> #include <vector> using namespace std; // Function to find the smallest // divisor such that the sum // of divisions is <= K int smallestDivisor(vector< int >& nums, int K) { int left = 1, right = *max_element(nums.begin(), nums.end()); // Binary search to find // the smallest divisor while (left < right) { int mid = left + (right - left) / 2; int totalSum = 0; // Calculate the total sum of // divisions using the // current mid value for ( int num : nums) { // Round up the division result totalSum += (num + mid - 1) / mid; } // Adjust the search range // based on the totalSum if (totalSum <= K) { right = mid; } else { left = mid + 1; } } // Return the smallest divisor // that meets the condition return left; } // Drivers code int main() { vector< int > A = { 1, 2, 5, 9 }; int K = 6; int result = smallestDivisor(A, K); // Function Call cout << result << endl; return 0; } |
Java
import java.util.*; public class SmallestDivisor { // Function to find the smallest // divisor such that the sum // of divisions is <= K public static int smallestDivisor(ArrayList<Integer> nums, int K) { int left = 1 ; int right = Collections.max(nums); // Binary search to find // the smallest divisor while (left < right) { int mid = left + (right - left) / 2 ; int totalSum = 0 ; // Calculate the total sum of // divisions using the // current mid value for ( int num : nums) { // Round up the division result totalSum += (num + mid - 1 ) / mid; } // Adjust the search range // based on the totalSum if (totalSum <= K) { right = mid; } else { left = mid + 1 ; } } // Return the smallest divisor // that meets the condition return left; } // Driver code public static void main(String[] args) { ArrayList<Integer> A = new ArrayList<>(Arrays.asList( 1 , 2 , 5 , 9 )); int K = 6 ; int result = smallestDivisor(A, K); // Function Call System.out.println(result); } } |
Python3
import math # Function to find the smallest # divisor such that the sum # of divisions is <= K def smallestDivisor(nums, K): left = 1 right = max (nums) # Binary search to find # the smallest divisor while left < right: mid = left + (right - left) / / 2 total_sum = 0 # Calculate the total sum of # divisions using the # current mid value for num in nums: # Round up the division result total_sum + = (num + mid - 1 ) / / mid # Adjust the search range # based on the total_sum if total_sum < = K: right = mid else : left = mid + 1 # Return the smallest divisor # that meets the condition return left # Driver code if __name__ = = "__main__" : A = [ 1 , 2 , 5 , 9 ] K = 6 result = smallestDivisor(A, K) # Function Call print (result) # This code is contributed by shivamgupta310570 |
C#
// C# code for the above approach using System; using System.Collections.Generic; using System.Linq; public class GFG { // Function to find the smallest // divisor such that the sum // of divisions is <= K public static int SmallestDivisor(List< int > nums, int K) { int left = 1; int right = nums.Max(); // Binary search to find // the smallest divisor while (left < right) { int mid = left + (right - left) / 2; int totalSum = 0; // Calculate the total sum of // divisions using the // current mid value foreach ( int num in nums) { // Round up the division result totalSum += (num + mid - 1) / mid; } // Adjust the search range // based on the totalSum if (totalSum <= K) { right = mid; } else { left = mid + 1; } } // Return the smallest divisor // that meets the condition return left; } // Drivers code public static void Main( string [] args) { List< int > A = new List< int > { 1, 2, 5, 9 }; int K = 6; int result = SmallestDivisor(A, K); // Function Call Console.WriteLine(result); } } |
Javascript
// JS Implementation // Function to find the smallest // divisor such that the sum // of divisions is <= K function smallestDivisor(nums, K) { let left = 1; let right = Math.max(...nums); // Binary search to find // the smallest divisor while (left < right) { let mid = left + Math.floor((right - left) / 2); let totalSum = 0; // Calculate the total sum of // divisions using the // current mid value for (let num of nums) { // Round up the division result totalSum += Math.ceil(num / mid); } // Adjust the search range // based on the totalSum if (totalSum <= K) { right = mid; } else { left = mid + 1; } } // Return the smallest divisor // that meets the condition return left; } // Driver code const A = [1, 2, 5, 9]; const K = 6; const result = smallestDivisor(A, K); // Function Call console.log(result); // This code is contributed by Tapesh(tapeshdua420) |
Output
5
Time Complexity:
Auxiliary Space: