Minimum count of balls in a bag
You are given an integer array ‘ARR’ of size ‘N’, where ‘ARR[i]’ denotes the number of balls in the ‘i-th’ bag. You are also given an integer ‘M’, denoting the maximum number of operations you can perform on ‘ARR’ (the given collection of bags).

In each operation, you can do the following:

Choose a bag from the collection and divide it into two new bags such that each bag contains a positive (non-zero) number of balls. Remove the chosen bag from the collection and add the new bags into the collection.

After performing the operations, let ‘X’ be the maximum number of balls in a bag. The task is to find the minimum possible value of ‘X’ and return it.

Example:

ARR = [5, 7], N = 2, M = 2 Perform the following two operations on ‘ARR’: 1. Divide the bag with 7 balls into 3 and 4. New ARR = [3, 4, 5]. 2. Divide the bag with 5 balls into 1 and 4. New ARR = [1, 3, 4, 4]. The bag with the maximum number of balls has 4 balls. Hence, the minimum possible value of ‘X’ is 4. Return 4 as the answer.

Note:

1. You can perform any number of operations between [0, M], both included. 2. Avoid using the 'Modulo' operator as it can cause Time Limit Exceeded.

Input format:

The first line of input contains an integer ‘T’ which denotes the number of test cases. Then, the ‘T’ test cases follow. The first line of each test case contains two space-separated integers, ‘N’ and ‘M’, denoting the size of array ‘ARR’ and the maximum number of operations. The second line of each test case contains ‘N’ space-separated integers denoting the elements of array ‘ARR’.

Output format:

For every test case, return the minimum possible value of ‘X’.

Note:

You do not need to print anything; it has already been taken care of. Just implement the function.

Constraints:

1

Question

Minimum count of balls in a bag

You are given an integer array ‘ARR’ of size ‘N’, where ‘ARR[i]’ denotes the number of balls in the ‘i-th’ bag. You are also given an integer ‘M’, denoting the maximum number of operations you can perform on ‘ARR’ (the given collection of bags).

In each operation, you can do the following:

Choose a bag from the collection and divide it into two new bags such that each bag contains a positive (non-zero) number of balls. Remove the chosen bag from the collection and add the new bags into the collection.

After performing the operations, let ‘X’ be the maximum number of balls in a bag. The task is to find the minimum possible value of ‘X’ and return it.

Example:

ARR = [5, 7], N = 2, M = 2

Perform the following two operations on ‘ARR’: 
1. Divide the bag with 7 balls into 3 and 4. New ARR = [3, 4, 5].
2. Divide the bag with 5 balls into 1 and 4. New ARR = [1, 3, 4, 4].

The bag with the maximum number of balls has 4 balls. Hence, the minimum possible value of ‘X’ is 4. Return 4 as the answer.

Note:

1. You can perform any number of operations between [0, M], both included.
2. Avoid using the 'Modulo' operator as it can cause Time Limit Exceeded.

Input format:

The first line of input contains an integer ‘T’ which denotes the number of test cases. Then, the ‘T’ test cases follow.

The first line of each test case contains two space-separated integers, ‘N’ and ‘M’, denoting the size of array ‘ARR’ and the maximum number of operations.

The second line of each test case contains ‘N’ space-separated integers denoting the elements of array ‘ARR’.

Output format:

For every test case, return the minimum possible value of ‘X’.

Note:

You do not need to print anything; it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10
1 <= N, M <= 10^3
1 <= ARR[i] <= 10^6

Time limit: 1 sec

Accepted Answer

Brute force

Let 'X' be the maximum number of balls in a bag that we desire. Let ‘COUNT[i]’ be the number of operations that we need to perform on ‘ARR[i]’ such that the new bags made from it contain less than or equal to 'X' balls. Consider the following examples:

If we want 'X' to be ‘4’, then:

‘ARR[i] = 5’, after splitting we get [4, 1], so ‘COUNT[i] = 1’

‘ARR[i] = 8’, after splitting we get [4, 4] so ‘COUNT[i] = 1’

‘ARR[i] = 9’, after splitting we get [4, 5] => [4, 4, 1] so ‘COUNT[i] = 2’

‘ARR[i] = 12’, after splitting we get [4, 8] => [4, 4, 4] so ‘COUNT[i] = 2’

‘ARR[i] = 13’, after splitting we get [4, 9] => [4, 4, 5] => [4, 4, 4, 1] so ‘COUNT[i] = 3’

‘ARR[i] = 15’, after splitting we get [4, 11] => [4, 4, 7] => [4, 4, 4, 3] so ‘COUNT[i] = 3’

After observing we can see that: ‘COUNT[i] = (ARR[i] - 1)/x’. This is because if 'X' divides ‘ARR[i]’ then we don’t need to split the last bag, see the above two examples where ‘ARR[i] = 12’ and ‘ARR[i] = 13’ for more clarity.

Let ‘OPERATIONS’ be the number of operations we need to perform on ‘ARR’ to get the desired 'X', ‘OPERATIONS = summation(COUNT[i])’. Let ‘HIGH’ be the maximum number of balls in a bag. So, 'X' varies from 1 to ‘HIGH’. We now iterate through the values of 'X' until we find a value that has ‘OPERATIONS’ less than or equal to ‘m’. Following are the steps to obtain 'X':

Initialize two integers ‘HIGH = the maximum number of balls in a bag’ and 'RESULT'. Use 'RESULT' to store the answer.
Run a loop where 'X' ranges from 1 to ‘HIGH’:
- ‘OPERATIONS = 0’
- Run a loop where ‘i’ ranges from 0 to ‘N-1’:
  - ‘OPERATIONS += (ARR[i] - 1)/X’
- If ‘OPERATIONS’ is less than equal to ‘M’, then:
  - ‘RESULT = X’
  - Break the loop.
Return 'RESULT' as the answer.

Space Complexity: O(1)Explanation:

O(1).

Since we are not using any extra space, space complexity is constant.

Time Complexity: OtherExplanation:

O(N * MAX), where ‘N’ is the size of array ‘ARR’ and ‘MAX’ is the maximum value in ‘ARR’.

We run a single loop from 1 to ‘MAX’, i.e., for ‘MAX’ iterations. In each such iteration, we loop over ‘ARR’ to compute ‘OPERATIONS’ in ‘O(N)’. Hence, the time complexity ‘O(N * MAX).

Python (3.5)

'''

    Time Complexity : O(N * MAX)

    Space Complexity : O(1)



    where 'N' is the size of array 'ARR' and 'MAX' is the maximum value in 'ARR'.

'''



def minCountOfBallsInBag(arr,  n,  m):



    # Get the maximum value in 'arr'.

    high = max(arr)



    for x in range(1, high + 1):



        operations = 0



        # The number of operations we need to perform on 'arr' to get 'x' as the maximum value.

        for i in range(n):

            operations += (arr[i] - 1)//x



        # If operations required less than 'm' then answer is 'x'.

        if (operations <= m):

            return x

Java (SE 1.8)

/*
    Time Complexity : O(N * MAX)
    Space Complexity : O(1)

    where 'N' is the size of array 'ARR' and 'MAX' is the maximum value in 'ARR'.
*/
    
import java.util.ArrayList;

public class Solution {
    public static int minCountOfBallsInBag(ArrayList arr, int n, int m) {
        int high = 1, result = 0;
        int operations = 0;

        for (int i = 0; i < n; i++) {  
            // Get the maximum value in 'arr'.
            high = Math.max(high, arr.get(i));
        }

        for (int x = 1; x <= high; x++) {
            operations = 0;

            /*
                The number of operations we need to perform on 'arr' to get 
                'x' as the maximum value.
            */
            for (int i = 0; i < n; i++) {
                operations += (arr.get(i) - 1) / x;
            }

            // Store value of 'x' in 'result' and break the loop.
            if (operations <= m) {
                result = x;
                break;
            }
        }

        return result;
    }
}

C++ (g++ 5.4)

/*
    Time Complexity : O(N * MAX)
    Space Complexity : O(1)

    where 'N' is the size of array 'ARR' and 'MAX' is the maximum value in 'ARR'.
*/

int minCountOfBallsInBag(vector &arr, int n, int m) {
    int high = 1, result;
    int operations;

    for (int i = 0; i < n; i++) {  
        // Get the maximum value in 'arr'.
        high = max(high, arr[i]);
    }

    for (int x = 1; x <= high; x++) {
        operations = 0;

        /*
            The number of operations we need to perform on 'arr' to get 
            'x' as the maximum value.
        */
        for (int i = 0; i < n; i++) {
            operations += (arr[i] - 1) / x;
        }

        // Store value of 'x' in 'result' and break the loop.
        if (operations <= m) {
            result = x;
            break;
        }
    }

    return result;
}

Accepted Answer

Binary search with validation

Let 'X' be the maximum number of balls in a bag that we desire. Let ‘COUNT[i]’ be the number of operations that we need to perform on ‘ARR[i]’ such that the new bags made from it contain less than or equal to 'X' balls. We have,

‘COUNT[i] = (ARR[i] - 1)/X’

Let ‘OPERATIONS’ be the number of operations we need to perform on ‘ARR’ to get the desired 'X', ‘OPERATIONS = summation(COUNT[i])’. Let ‘HIGH’ be the maximum number of balls in a bag. So, 'X' varies from 1 to ‘HIGH’. We can use binary search to find the smallest value of 'X', which has ‘OPERATIONS’ less than or equal to ‘m’. Following are the steps to obtain 'X':

Initialize three integers ‘LOW = 1’, ‘MID’, and ‘HIGH = the maximum number of balls in a bag’.
Run a loop until ‘LOW’ is less than ‘HIGH’:
- ‘MID = (LOW + HIGH)/2’
- ‘OPERATIONS = 0’
- Run a loop where ‘i’ ranges from 0 to ‘n-1’:
  - ‘OPERATIONS += (ARR[i] - 1)/MID’
- If ‘OPERATIONS’ is greater than ‘m’, then we need to move to a larger value of 'X' (i.e., ‘X +1 = MID + 1’) to reduce ‘OPERATIONS’, so:
  - ‘LEFT = MID + 1’
- Else, we store the current value of 'X' (i.e., ‘MID’) as we can reach it in ‘m’ operations, and in the next iteration, we check if a smaller value of 'X' is possible, so:
  - ‘HIGH = MID’
Return ‘HIGH’ as the answer.

Space Complexity: O(1)Explanation:

O(1).

Since we are not using any extra space, space complexity is constant.

Time Complexity: OtherExplanation:

O(N * log(MAX)), where ‘N’ is the size of array ‘ARR’ and 'MAX’ is the maximum value in ‘ARR’.

The binary search runs from 1 to ‘MAX’, i.e., for ‘log(MAX)’ iterations. In each iteration, we run a loop over the array ‘ARR’ to compute ‘operations’ in ‘O(N)’. Hence, the time complexity ‘O(N*log(MAX))’.

C++ (g++ 5.4)

/*
    Time Complexity : O(N * log(MAX))
    Space Complexity : O(1)

    where 'N' is the size of array 'ARR' and 'MAX' is the maximum value in 'ARR'.
*/

int minCountOfBallsInBag(vector &arr, int n, int m) {
    int low = 1, high = 1, mid;
    int operations;

    for (int i = 0; i < n; i++) {  
        // Get the maximum value in 'arr'.
        high = max(high, arr[i]);
    }

    while (low < high) {
        mid = (high + low) / 2;
        operations = 0;

        // The number of operations we need to perform on 'arr' to get 'x' = 'mid'.
        for (int i = 0; i < n; i++) {
            operations += (arr[i] - 1) / mid;
        }

        /*
            All 'x' less than equal to 'mid' need more than 'm' operations
            So, in next iteration search from 'mid + 1' to 'high'.
        */
        if (operations > m) {
            low = mid + 1;
        }
        /*
            'mid' is a valid value of 'x', we need to check if any lesser value is possible
            So, in next iteration search from 'low' to 'mid'.
        */
        else {
            high = mid;
        }
    }

    return high;
}

Python (3.5)

'''

    Time Complexity : O(N * log(MAX))

    Space Complexity : O(1)



    where 'N' is the size of array 'ARR' and 'MAX' is the maximum value in 'ARR'.

'''



def minCountOfBallsInBag(arr, n, m):



    low = 1

    high = 1



    # Get the maximum value in 'arr'.

    high = max(arr)



    while (low < high):



        mid = (high - low) // 2 + low

        operations = 0



        # The number of operations we need to perform on 'arr' to get 'x' = 'mid'.

        for i in range(n):



            operations += (arr[i] - 1)//mid



        # All 'x' less than equal to 'mid' need more than 'm' operations.

        # So, in next iteration search from 'mid + 1' to 'high'.

        if (operations > m):

            low = mid + 1



        # 'mid' is a valid value of 'x', we need to check if any lesser value is possible.

        # So, in next iteration search from 'low' to 'mid'.

        else:

            high = mid



    return high

Java (SE 1.8)

/*
    Time Complexity : O(N * log(MAX))
    Space Complexity : O(1)

    where 'N' is the size of array 'ARR' and 'MAX' is the maximum value in 'ARR'.
*/
    
import java.util.ArrayList;

public class Solution {
    public static int minCountOfBallsInBag(ArrayList arr, int n, int m) {
        int low = 1, high = 1, mid = 0;
        int operations = 0;

        for (int i = 0; i < n; i++) {  
            // Get the maximum value in 'arr'.
            high = Math.max(high, arr.get(i));
        }

        while (low < high) {
            mid = (high + low) / 2;
            operations = 0;

            // The number of operations we need to perform on 'arr' to get 'x' = 'mid'.
            for (int i = 0; i < n; i++) {
                operations += (arr.get(i) - 1) / mid;
            }

            /*
                All 'x' less than equal to 'mid' need more than 'm' operations
                So, in next iteration search from 'mid + 1' to 'high'.
            */
            if (operations > m) {
                low = mid + 1;
            }
            /*
                'mid' is a valid value of 'x', we need to check if any lesser value is possible
                So, in next iteration search from 'low' to 'mid'.
            */
            else {
                high = mid;
            }
        }

        return high;
    }
}

You are given an integer array ‘ARR’ of size ‘N’, where ‘ARR[i]’ denotes the number of balls in the ‘i-th’ bag. You are also given an integer ‘M’, denoting the maximum number of operations you can perform on ‘ARR’ (the given collection of bags).

In each operation, you can do the following:

Choose a bag from the collection and divide it into two new bags such that each bag contains a positive (non-zero) number of balls. Remove the chosen bag from the collection and add the new bags into the collection.

After performing the operations, let ‘X’ be the maximum number of balls in a bag. The task is to find the minimum possible value of ‘X’ and return it.

Example:

Note:

Input format:

Output format:

Note:

Constraints:

Top HashedIn by Deloitte SDE-2 interview questions & answers

Popular interview questions of SDE-2

Top HR questions asked in HashedIn by Deloitte SDE-2