Distribute N candies among K people
Sanyam has ‘N’ candies, he wants to distribute that into ‘K’ of his friends. He made his ‘K’ friends stand in line, in increasing order of his likeness. Not being so smart he gives 1 candy to the first friend, 2 to the second person, and so on till the kth person. In the next turn, the first person gets ‘K + 1’ candies, the second person gets ‘K + 2’ candies, and so on.

While distributing the candies, if at a turn, the number of candies to be given to a friend is less than the required candies, then that friend gets all the remaining candies and Sanyam stops the distribution.

Your task is to find the total number of candies every person has at the end.

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases. The next ‘T’ lines represent the ‘T’ test cases. The first and only line of each test case contains two space-separated integers ‘N’ and ‘K’ denoting the number of candies and number of friends respectively.

Output Format:

For each test case, return the total number of candies every person has at the end.

Note:

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

Constraints:

1

Question

Distribute N candies among K people

Sanyam has ‘N’ candies, he wants to distribute that into ‘K’ of his friends. He made his ‘K’ friends stand in line, in increasing order of his likeness. Not being so smart he gives 1 candy to the first friend, 2 to the second person, and so on till the kth person. In the next turn, the first person gets ‘K + 1’ candies, the second person gets ‘K + 2’ candies, and so on.

While distributing the candies, if at a turn, the number of candies to be given to a friend is less than the required candies, then that friend gets all the remaining candies and Sanyam stops the distribution.

Your task is to find the total number of candies every person has at the end.

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The next ‘T’ lines represent the ‘T’ test cases.

The first and only line of each test case contains two space-separated integers ‘N’ and ‘K’ denoting the number of candies and number of friends respectively.

Output Format:

For each test case, return the total number of candies every person has at the end.

Note:

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

Constraints:

1 <= T <= 50
1 <= N <= 10^9
1 <= K <= 10^5

Time Limit: 1 sec

Accepted Answer

Brute Force

Here we can simply use the concept of brute force.

We initialize an array with 0 elements.
Then we make a variable and initialize it with 1(let’s call it “increment”). This variable is used to keep track of the number of candies to be given to the current friend.
We start with the first element and increase it by ‘increment’.
Now we reduce the total number of candies by the variable ‘increment’. (N = N - increment).
Now we increase the value of ‘increment’ by 1.
In the left ‘N’ is less than ‘increment’ we make ‘increment’ equal to ‘N’. Because as written in the question the number of candies left is less than the candies to be given then all left candies will be given to the friend.
We go to the next element and continue doing that.
If we reach the end of the array we will go to the first element again for the next round of distribution.
If the total number of candies is 0 we stop the iteration.

Space Complexity: O(n)Explanation:

O(K), where ‘K is the total number of friends.

An array of size ‘K’ is used to store the candies of every friend.

Time Complexity: OtherExplanation:

O(K * (total number of turns)), where ‘K is the total number of friends.

Since we are considering each possibility of dividing candies, the total complexity is O(K * (total number of turns)).

Accepted Answer

Mathematical approach

We initialize an array with 0 elements.
We know that 1 + 2 + 3……+ r = ((r * (r + 1)) / 2).
We can sum of natural numbers till the last term of the series which will be (turns * K) and subtracting the sum of natural numbers till the last term of the previous series which is (turns - 1) * K.
Keep doing this till the sum is less than ‘N’, once it exceeds then distribute candies in the given way till possible.
We call a turn completed if every person gets the desired number of candies he is to get in a turn.
We will assign the left candies in brute force way only.

Space Complexity: O(n)Explanation:

O(K), where ’K' is the total number of his friends.

An array of size ‘K’ is used to store the candies of every friend.

Time Complexity: OtherExplanation:

O(total number of turns + K), where ‘K is the total number of his friends.

We will find the number of turns so it will take that number of iterations and we have to visit every friend to assign the total number of candies to him. So log(N) + k number of time iteration.

Accepted Answer

Binary search

Here we can simply use the concept of binary search.

We initialize an array with 0 elements.
We use binary search to find the largest ‘x’ which satisfies x * (x + 1) <= (2 * N). (Here x is the total number of times Sanyam will distribute the candy to his friend). A binary search will help us to locate the number of times Sanyam is giving candy to his friend.
Now we need to calculate the number of times it will visit an ith friend in the ‘x’ iteration.
Use arithmetic progression to find the sum in the ‘r’ iteration
- (rth term:- i + (r - 1) * k).
Make N = N - (x * (x + 1)) / 2 and x = x + 1. (We are doing this last part to make sure that the left part of candies are being given to the next friend, as mentioned in the question that the left candies are required to be given to the next friend.)
Take x mod by k. (x = x % K);
Increase ‘xth’ term by N.

Space Complexity: O(n)Explanation:

O(K), where ’K’ is the total number of his friends.

An array of size ‘K’ is used to store the candies of every friend.

Time Complexity: OtherExplanation:

O(log(N) + K), where ‘N’ is the total number of candies and ‘K’ is the total number of his friends.

Binary search will take log(N) time and we have to visit every friend to assign the total number of candies to him, which takes time of order ‘K’.

While distributing the candies, if at a turn, the number of candies to be given to a friend is less than the required candies, then that friend gets all the remaining candies and Sanyam stops the distribution.

Your task is to find the total number of candies every person has at the end.

Input Format:

Output Format:

Note:

Constraints:

Top GeeksForGeeks Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in GeeksForGeeks Software Developer