Minimum Count of Balls in a Bag Problem Statement

You are given an integer array ARR of size N, where ARR[i] represents the number of balls in the i-th bag. Additionally, you have an integer M, which indicates the maximum number of operations you can perform on this collection of bags.

Explanation:

In each operation, you have the option to choose a bag from the collection and split it into two new bags in such a way that each bag contains a positive number of balls. The original bag is then removed from the collection, and the new bags are added.

Your task is to determine the minimum possible value of X, where X is the maximum number of balls in a bag after performing the operations, and return this value.

Input:

The first line of input contains an integer ‘T’ indicating the number of test cases. For each test case, the following inputs are given:
- First line: Two space-separated integers ‘N’ and ‘M’, the size of the array ‘ARR’ and the maximum number of operations.
- Second line: ‘N’ space-separated integers representing the elements of the array ‘ARR’.

Output:

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

Example:

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

Operations:
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 maximum number of balls in a bag is 4. Therefore, the minimum possible value of ‘X’ is 4. Return 4 as the result.

Constraints:

  • 1 <= T <= 10
  • 1 <= N, M <= 103
  • 1 <= ARR[i] <= 106
  • Time limit: 1 sec

Note:

1. You can perform any number of operations between [0, M], both inclusive.
2. Avoid using the 'Modulo' operator as it can lead to exceeding time limits.
AnswerBot
2d

Find the minimum possible value of the maximum number of balls in a bag after performing a given number of operations.

  • Iterate through the bags and split them to minimize the maximum number of balls.

  • Ke...read more

Help your peers!
Add answer anonymously...
HashedIn by Deloitte SDE-2 Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter