Distribute N candies among K people

Easy
0/40
Average time to solve is 15m
profile
Contributed by
14 upvotes
Asked in companies
OlaIntuitGeeksforGeeks

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
7 4
4 1
Sample Output 1:
1 2 3 1
4
Explanation For Sample Input1:
Test case 1:
Sanyam has 7 candies and 4 friends.
In the first turn, the first friend gets 1 candy, the second friend gets 2 candies and the third friend gets 3 candies. Now he has used up 6 candies and 1 candy is left. As per the condition, the fourth friend has to be given 4 candies, but there is only 1 left, hence he takes one only. 

Test case 2:
As there is only one friend he will get the first candy, then the next two, and then the last one making the count 4.
Sample Input 2:
2
10 3
3 2
Sample Output 2:
5 2 3 
1 2
Hint

Try to do as asked in the problem and simply give candy to every friend one by one.

Approaches (3)
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.
Time Complexity

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)).

Space Complexity

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

 

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

Code Solution
(100% EXP penalty)
Distribute N candies among K people
Full screen
Console