Find the smallest divisor

Intuition:

The extremely naive approach is to use linear search to check all possible divisors from 1 to maximum element of the array. The minimum number for which the result is less than or equal to threshold value(limit), will be our answer.

Approach:

Traverse from 1 to maximum element of the array to check all possible divisors.
Within this loop, divide each element in the array by the current divisor, and sum up the obtained ceiling values.
If result is less than or equal to threshold, return the current divisor as our answer.
Finally, if we are outside the nested loops, return -1 as no such divisor is found.

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to find the smallest divisor
    int smallestDivisor(vector<int>& nums, int limit) {
        // Size of array.
        int n = nums.size(); 
        
        // Find the maximum element in arr
        int maxi = *max_element(nums.begin(), nums.end());

        // Find the smallest divisor
        for (int d = 1; d <= maxi; d++) {
            int sum = 0;
            
            /* Calculate the sum of ceil
            (nums[i] / d) for all elements*/
            for (int i = 0; i < n; i++) {
                sum += ceil((double)nums[i] / (double)d);
            }
            
            // Check if the sum is <= limit
            if (sum <= limit)
                return d;
        }
        
        // Return -1 if no valid divisor found
        return -1;
    }
};

int main() {
    vector<int> arr = {1, 2, 3, 4, 5};
    int limit = 8;
    
    // Create an object of the Solution class
    Solution sol;
    
    int ans = sol.smallestDivisor(arr, limit);
    
    // Print the result
    cout << "The minimum divisor is: " << ans << "\n";
    
    return 0;
}
import java.util.*;

class Solution {
    // Function to find the smallest divisor
    public int smallestDivisor(int[] nums, int limit) {
        // Size of array
        int n = nums.length;

        // Find the maximum element in nums
        int maxi = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            maxi = Math.max(maxi, nums[i]);
        }

        // Find the smallest divisor
        for (int d = 1; d <= maxi; d++) {
            int sum = 0;

            /* Calculate the sum of ceil
            (nums.get(i) / d) for all elements */
            for (int i = 0; i < n; i++) {
                sum += Math.ceil((double) nums[i] / (double)(d));
            }

            // Check if the sum is <= limit
            if (sum <= limit)
                return d;
        }

        // Return -1 if no valid divisor found
        return -1;
    }

    public static void main(String[] args) {
       int[] nums = {1, 2, 3, 4, 5};
        int limit = 8;

        // Create an object of the Solution class
        Solution sol = new Solution();

        int ans = sol.smallestDivisor(nums, limit);

        // Print the result
        System.out.println("The minimum divisor is: " + ans);
    }
}
import math

class Solution:
    # Function to find the smallest divisor
    def smallestDivisor(self, nums, limit):
        # Size of array
        n = len(nums)

        # Find the maximum element in nums
        maxi = max(nums)

        # Find the smallest divisor
        for d in range(1, maxi + 1):
            sum = 0

            """ Calculate the sum of ceil
            (nums[i] / d) for all elements """
            for num in nums:
                sum += math.ceil(num / d)

            # Check if the sum is <= limit
            if sum <= limit:
                return d

        # Return -1 if no valid divisor found
        return -1

if __name__ == "__main__":
    nums = [1, 2, 3, 4, 5]
    limit = 8

    # Create an object of the Solution class
    sol = Solution()

    ans = sol.smallestDivisor(nums, limit)

    # Print the result
    print(f"The minimum divisor is: {ans}")
class Solution {
    // Function to find the smallest divisor
    smallestDivisor(nums, limit) {
        // Size of array
        let n = nums.length;

        // Find the maximum element in nums
        let maxi = Math.max(...nums);

        // Find the smallest divisor
        for (let d = 1; d <= maxi; d++) {
            let sum = 0;

            /* Calculate the sum of ceil
            (nums[i] / d) for all elements */
            for (let i = 0; i < n; i++) {
                sum += Math.ceil(nums[i] / d);
            }

            // Check if the sum is <= limit
            if (sum <= limit)
                return d;
        }

        // Return -1 if no valid divisor found
        return -1;
    }
}

let arr = [1, 2, 3, 4, 5];
let limit = 8;

// Create an object of the Solution class
let sol = new Solution();

let ans = sol.smallestDivisor(arr, limit);

// Print the result
console.log(`The minimum divisor is: ${ans}`);

Complexity Analysis:

Time Complexity:O(max*N), where max is the maximum element in the array, N is size of the array. As nested loops are being used. The outer loop runs from 1 to max and the inner loop runs for N times.

Space Complexity: As no additional space is used, so the Space Complexity is O(1).

Intuition:

Here the idea is to use binary search to efficiently solve this problem by dividing the search space into halves. As, the search space of this probem is in the range[1, max], where max is the maximum element of the array. It can be considered as a sorted search space, hence binary search can be applied.

Approach:

Working of smallestDivisor(nums, limit):

Iterate using while (low less than or equal to high) to find the smallest divisor.
Compute mid as the midpoint between low and high. Mid would be representing the current divisor.
Use the helper function sumByD(nums, mid) to check if the summation of division values for mid is less than or equal to limit, if yes, eliminate the left half of the search space. Else, eliminate the right half, as we need to find a greater divisor.

Working of sumByD(nums, limit):

Initialize 'n' to the size of nums, 'sum' is initialized to zero, which will accumulate the sum of division results.
Iterate through each element in the array using a for-loop. For each element, the division result is computed. This division result is cast to double to ensure floating-point precision. The ceil function is applied to round up the division result to the nearest integer. This ensures that even if there's a fractional part, it is rounded up.
The rounded-up division result is added to 'sum' in each iteration of the loop. This accumulates the total sum of all such rounded-up division results for all elements in nums.
Finally, after iterating through all elements in array, the return the accumulated sum, which represents the total sum of division results rounded up to the nearest integer for each element divided by limit.

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    /* Helper function to find the
    summation of division values*/
    int sumByD(vector<int>& nums, int limit) {
        // Size of array
        int n = nums.size(); 
        
        // Find the summation of division values
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += ceil((double)(nums[i]) / (double)(limit));
        }
        return sum;
    }

public:
    // Function to find the smallest divisor
    int smallestDivisor(vector<int>& nums, int limit) {
        int n = nums.size();
        if (n > limit) return -1;
        
        // Initialize binary search bounds
        int low = 1, high = *max_element(nums.begin(), nums.end());

        // Apply binary search
        while (low <= high) {
            int mid = (low + high) / 2;
            if (sumByD(nums, mid) <= limit) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
};

int main() {
    vector<int> nums = {1, 2, 3, 4, 5};
    int limit = 8;

    // Create an object of the Solution class
    Solution sol;

    int ans = sol.smallestDivisor(nums, limit);

    // Print the result
    cout << "The minimum divisor is: " << ans << "\n";

    return 0;
}
import java.util.Arrays;

class Solution {
    /* Helper unction to find the 
    summation of division values */
    private int sumByD(int[] nums, int limit) {
        // Size of array
        int n = nums.length; 
        
        // Find the summation of division values
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += Math.ceil((double)nums[i] / (double)limit);
        }
        return sum;
    }

    // Function to find the smallest divisor
    public int smallestDivisor(int[] nums, int limit) {
        int n = nums.length;
        if (n > limit) return -1;
        
        //Find the maximum element:
        int maxi = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            maxi = Math.max(maxi, nums[i]);
        }

        int low = 1, high = maxi;

        // Apply binary search
        while (low <= high) {
            int mid = (low + high) / 2;
            if (sumByD(nums, mid) <= limit) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        int limit = 8;

        // Create an object of the Solution class
        Solution sol = new Solution();

        int ans = sol.smallestDivisor(nums, limit);

        // Print the result
        System.out.println("The minimum divisor is: " + ans);
    }
}
import math

class Solution:
    """ Helper function to find the 
    summation of division values"""
    def sumByD(self, nums, limit):
        # Size of array
        n = len(nums)  
        
        # Find the summation of division values
        sum_val = 0
        for num in nums:
            sum_val += math.ceil(num / limit)
        return sum_val

    # Function to find the smallest divisor
    def smallestDivisor(self, nums, limit):
        n = len(nums)
        if n > limit:
            return -1
        
        # Initialize binary search bounds
        low = 1
        high = max(nums)

        # Apply binary search
        while low <= high:
            mid = (low + high) // 2
            if self.sumByD(nums, mid) <= limit:
                high = mid - 1
            else:
                low = mid + 1
        #Return the answer
        return low

if __name__ == "__main__":
    nums = [1, 2, 3, 4, 5]
    limit = 8

    # Create an object of the Solution class
    sol = Solution()

    ans = sol.smallestDivisor(nums, limit)

    # Print the result
    print(f"The minimum divisor is: {ans}")
class Solution {
    /* Helper function to find the 
    summation of division values*/
    sumByD(nums, limit) {
        // Size of array
        const n = nums.length; 
        
        // Find the summation of division values
        let sum = 0;
        for (let i = 0; i < n; i++) {
            sum += Math.ceil(nums[i] / limit);
        }
        return sum;
    }

    // Function to find the smallest divisor
    smallestDivisor(nums, limit) {
        const n = nums.length;
        if (n > limit) return -1;
        
        // Initialize binary search bounds
        let low = 1, high = Math.max(...nums);

        // Apply binary search
        while (low <= high) {
            let mid = Math.floor((low + high) / 2);
            if (this.sumByD(nums, mid) <= limit) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        //Return the answer
        return low;
    }
}

function main() {
    const nums = [1, 2, 3, 4, 5];
    const limit = 8;

    // Create an object of the Solution class
    const sol = new Solution();

    const ans = sol.smallestDivisor(nums, limit);

    // Print the result
    console.log(`The minimum divisor is: ${ans}`);
}
main();

Complexity Analysis:

Time Complexity:O(log(max)*N), where max is the maximum element in the array, N is size of the array.

We are applying binary search on our answers that are in the range of [1, max]. For every possible divisor ‘mid’, calling the sumByD() function. Inside that function, traversing the entire array, which results in O(N).

Space Complexity: As no additional space is used, so the Space Complexity is O(1).

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Approach:

Complexity Analysis:

Intuition:

Approach:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code