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.
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.
For each test case, return the total number of candies every person has at the end.
You do not need to print anything; it has already been taken care of. Just implement the given functions.
1 <= T <= 50
1 <= N <= 10^9
1 <= K <= 10^5
Time Limit: 1 sec
2
7 4
4 1
1 2 3 1
4
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.
2
10 3
3 2
5 2 3
1 2
Try to do as asked in the problem and simply give candy to every friend one by one.
Here we can simply use the concept of brute force.
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)).
O(K), where ‘K is the total number of friends.
An array of size ‘K’ is used to store the candies of every friend.
All tags
Sort by
Interview problems
Easy solution just recap module
// tc o(n)
// sc o(n)
#include <bits/stdc++.h>
vector<int> candies(int n, int k)
{
int f[k]={0};
int i=1;
int j=0;
while(n!=0)
{
if (n < i) {
f[j%(k)] += n;
break;
}
else
f[j%(k)]+=i;
n=n-i;
i++;
j++;
}
vector<int>ans;
for(int i=0;i<k;i++)
{
ans.push_back(f[i]);
}
return ans;
}
Interview problems
PYTHON || Distribute N candies among K people
from os import *
from sys import *
from collections import *
from math import *
from sys import stdin
from sys import stdin
def candies(n, k):
a = [0] * k
i, p, q = 0, 1, n
if k == 1:
a[0] = n
return a
while q != 0:
if i >= k:
i = 0
if p > q:
p = q
a[i] += p
i += 1
p += 1
q = 0
break
else:
a[i] += p
i += 1
q -= p
p += 1
return a
def takeInput():
line = stdin.readline().split()
N = int(line[0])
K = int(line[1])
return N, K
t = int(stdin.readline())
for _ in range(t):
N, K = takeInput()
result = candies(N, K)
print(*result)
Interview problems
easy cpp
#include <bits/stdc++.h>
vector<int> candies(int n, int k) {
vector<int> ans(k, 0);
// 1st turn
for (int i = 0; i < k; i++) {
if (n >= i + 1) {
ans[i] = i + 1;
n = n - (i + 1);
} else {
ans[i] = n;
n = 0;
}
}
int j=0;
while (n != 0) {
j++;
for (int i = 0; i < k; i++) {
if (n >=j*k+ i + 1) {
ans[i] =ans[i]+( j*k +1+i);
n = n - (j*k + 1+i);
} else {
ans[i] =ans[i]+ n;
n = 0;
}
}
}
return ans;
}
Interview problems
easy c++ code || upvote if this code helped
vector<int> candies(int n, int k)
{
// Write your code here
int i=0;
int j=1;
vector<int>ans (k,0);
while(n>0)
{
ans[i%k] += min(n,j);
n=n-j;
j++;
i++;
}
return ans;
}
Interview problems
java
import java.util.* ;
import java.io.*;
public class Solution
{
public static int[] candies(int n, int k)
{
// Write your code here
int []a=new int[k];
int i=0,p=1,q=n;
if(k==1){
a[0]=n;
return a;
}
while(q!=0){
if(i>=k){
i=0;
}if(p>q){
p=q;
a[i]=a[i]+p;
i++;
p++;
q=0;
break;
}else if(p<=q){
a[i]=a[i]+p;
i++;
q=q-p;
p++;
}
}
return a;
}
}
Interview problems
easy c++ solution
#include <bits/stdc++.h>
vector<int> candies(int n, int k)
{
// Write your code here
vector<int> v(k); // define a vector of k length
int i=0;
while(n>0){
int candies = i+1;
v[i%k] += min(n,candies);
n = n-candies;
i++;
}
return v;
}
Interview problems
Discussion thread on Interview Problem | Distribute N candies among K people
Hey everyone, creating this thread to discuss the interview problem - Distribute N candies among K people.
Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Distribute N candies among K people
