Given N candies and K people. In the first turn, the first person gets 1 candy, the second gets 2 candies, and so on till K people. In the next turn, the first person gets K+1 candies, the second person gets k+2 candies, and so on. If the number of candies is less than the required number of candies at every turn, then the person receives the remaining number of candies.
The task is to find the total number of candies every person has at the end.
Examples:
Input: N = 7, K = 4
Output: 1 2 3 1
At the first turn, the fourth people has to be given 4 candies, but there is
only 1 left, hence he takes one only.Input: N = 10, K = 3
Output: 5 2 3
At the second turn first one receives 4 and then we have no more candies left.
Recommended Practice
A naive approach is to iterate for every turn and distribute candies accordingly till candies are finished.
Time complexity: O(Number of distributions)
A better approach is to perform every turn in O(1) by calculating sum of natural numbers till the last term of series which will be (turns*k) and subtracting the sum of natural numbers till the last term of 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.
Below is the implementation of the above approach:
C++
// C++ code for better approach
// to distribute candies
#include <bits/stdc++.h>
using
namespace
std;
// Function to find out the number of
// candies every person received
void
candies(
int
n,
int
k)
{
// Count number of complete turns
int
count = 0;
// Get the last term
int
ind = 1;
// Stores the number of candies
int
arr[k];
memset
(arr, 0,
sizeof
(arr));
while
(n) {
// Last term of last and
// current series
int
f1 = (ind - 1) * k;
int
f2 = ind * k;
// Sum of current and last series
int
sum1 = (f1 * (f1 + 1)) / 2;
int
sum2 = (f2 * (f2 + 1)) / 2;
// Sum of current series only
int
res = sum2 - sum1;
// If sum of current is less than N
if
(res <= n) {
count++;
n -= res;
ind++;
}
else
// Individually distribute
{
int
i = 0;
// First term
int
term = ((ind - 1) * k) + 1;
// Distribute candies till there
while
(n > 0) {
// Candies available
if
(term <= n) {
arr[i++] = term;
n -= term;
term++;
}
else
// Not available
{
arr[i++] = n;
n = 0;
}
}
}
}
// Count the total candies
for
(
int
i = 0; i < k; i++)
arr[i] += (count * (i + 1))
+ (k * (count * (count - 1)) / 2);
// Print the total candies
for
(
int
i = 0; i < k; i++)
cout << arr[i] <<
" "
;
}
// Driver Code
int
main()
{
int
n = 10, k = 3;
candies(n, k);
return
0;
}
Java
// Java code for better approach
// to distribute candies
class
GFG {
// Function to find out the number of
// candies every person received
static
void
candies(
int
n,
int
k){
int
[] arr =
new
int
[k];
int
j =
0
;
while
(n>
0
){
for
(
int
i =
0
;i<k;i++){
j++;
if
(n<=
0
){
break
;
}
else
{
if
(j<n){
arr[i] = arr[i]+j;
}
else
{
arr[i] = arr[i]+n;
}
n = n-j;
}
}
}
for
(
int
i:arr){
System.out.print(i+
" "
);
}
}
// Driver Code
public
static
void
main(String[] args)
{
int
n =
10
, k =
3
;
candies(n, k);
}
}
// This code is contributed by ihritik
Python3
# Python3 code for better approach
# to distribute candies
import
math as mt
# Function to find out the number of
# candies every person received
def
candies(n, k):
# Count number of complete turns
count
=
0
# Get the last term
ind
=
1
# Stores the number of candies
arr
=
[
0
for
i
in
range
(k)]
while
n >
0
:
# Last term of last and
# current series
f1
=
(ind
-
1
)
*
k
f2
=
ind
*
k
# Sum of current and last series
sum1
=
(f1
*
(f1
+
1
))
/
/
2
sum2
=
(f2
*
(f2
+
1
))
/
/
2
# Sum of current series only
res
=
sum2
-
sum1
# If sum of current is less than N
if
(res <
=
n):
count
+
=
1
n
-
=
res
ind
+
=
1
else
:
# Individually distribute
i
=
0
# First term
term
=
((ind
-
1
)
*
k)
+
1
# Distribute candies till there
while
(n >
0
):
# Candies available
if
(term <
=
n):
arr[i]
=
term
i
+
=
1
n
-
=
term
term
+
=
1
else
:
arr[i]
=
n
i
+
=
1
n
=
0
# Count the total candies
for
i
in
range
(k):
arr[i]
+
=
((count
*
(i
+
1
))
+
(k
*
(count
*
(count
-
1
))
/
/
2
))
# Print the total candies
for
i
in
range
(k):
print
(arr[i], end
=
" "
)
# Driver Code
n, k
=
10
,
3
candies(n, k)
# This code is contributed by Mohit kumar
C#
// C# code for better approach
// to distribute candies
using
System;
class
GFG
{
// Function to find out the number of
// candies every person received
static
void
candies(
int
n,
int
k)
{
// Count number of complete turns
int
count = 0;
// Get the last term
int
ind = 1;
// Stores the number of candies
int
[]arr=
new
int
[k];
for
(
int
i=0;i<k;i++)
arr[i]=0;
while
(n>0) {
// Last term of last and
// current series
int
f1 = (ind - 1) * k;
int
f2 = ind * k;
// Sum of current and last series
int
sum1 = (f1 * (f1 + 1)) / 2;
int
sum2 = (f2 * (f2 + 1)) / 2;
// Sum of current series only
int
res = sum2 - sum1;
// If sum of current is less than N
if
(res <= n) {
count++;
n -= res;
ind++;
}
else
// Individually distribute
{
int
i = 0;
// First term
int
term = ((ind - 1) * k) + 1;
// Distribute candies till there
while
(n > 0) {
// Candies available
if
(term <= n) {
arr[i++] = term;
n -= term;
term++;
}
else
// Not available
{
arr[i++] = n;
n = 0;
}
}
}
}
// Count the total candies
for
(
int
i = 0; i < k; i++)
arr[i] += (count * (i + 1))
+ (k * (count * (count - 1)) / 2);
// Print the total candies
for
(
int
i = 0; i < k; i++)
Console.Write( arr[i] +
" "
);
}
// Driver Code
public
static
void
Main()
{
int
n = 10, k = 3;
candies(n, k);
}
}
// This code is contributed by ihritik
PHP
<?php
// PHP code for better approach
// to distribute candies
// Function to find out the number of
// candies every person received
function
candies(
$n
,
$k
)
{
// Count number of complete turns
$count
= 0;
// Get the last term
$ind
= 1;
// Stores the number of candies
$arr
=
array_fill
(0,
$k
, 0) ;
while
(
$n
)
{
// Last term of last and
// current series
$f1
= (
$ind
- 1) *
$k
;
$f2
=
$ind
*
$k
;
// Sum of current and last series
$sum1
=
floor
((
$f1
* (
$f1
+ 1)) / 2);
$sum2
=
floor
((
$f2
* (
$f2
+ 1)) / 2);
// Sum of current series only
$res
=
$sum2
-
$sum1
;
// If sum of current is less than N
if
(
$res
<=
$n
)
{
$count
++;
$n
-=
$res
;
$ind
++;
}
else
// Individually distribute
{
$i
= 0;
// First term
$term
= ((
$ind
- 1) *
$k
) + 1;
// Distribute candies till there
while
(
$n
> 0)
{
// Candies available
if
(
$term
<=
$n
)
{
$arr
[
$i
++] =
$term
;
$n
-=
$term
;
$term
++;
}
else
// Not available
{
$arr
[
$i
++] =
$n
;
$n
= 0;
}
}
}
}
// Count the total candies
for
(
$i
= 0;
$i
<
$k
;
$i
++)
$arr
[
$i
] +=
floor
((
$count
* (
$i
+ 1)) + (
$k
*
(
$count
* (
$count
- 1)) / 2));
// Print the total candies
for
(
$i
= 0;
$i
<
$k
;
$i
++)
echo
$arr
[
$i
],
" "
;
}
// Driver Code
$n
= 10;
$k
= 3;
candies(
$n
,
$k
);
// This code is contributed by Ryuga
?>
Javascript
<script>
// JavaScript code for better approach
// to distribute candies
// Function to find out the number of
// candies every person received
function
candies(n , k) {
// Count number of complete turns
var
count = 0;
// Get the last term
var
ind = 1;
// Stores the number of candies
var
arr = Array(k);
for
(i = 0; i < k; i++)
arr[i] = 0;
while
(n > 0) {
// Last term of last and
// current series
var
f1 = (ind - 1) * k;
var
f2 = ind * k;
// Sum of current and last series
var
sum1 = (f1 * (f1 + 1)) / 2;
var
sum2 = (f2 * (f2 + 1)) / 2;
// Sum of current series only
var
res = sum2 - sum1;
// If sum of current is less than N
if
(res <= n) {
count++;
n -= res;
ind++;
}
else
// Individually distribute
{
var
i = 0;
// First term
var
term = ((ind - 1) * k) + 1;
// Distribute candies till there
while
(n > 0) {
// Candies available
if
(term <= n) {
arr[i++] = term;
n -= term;
term++;
}
else
// Not available
{
arr[i++] = n;
n = 0;
}
}
}
}
// Count the total candies
for
(i = 0; i < k; i++)
arr[i] += (count * (i + 1)) +
(k * (count * (count - 1)) / 2);
// Print the total candies
for
(i = 0; i < k; i++)
document.write(arr[i] +
" "
);
}
// Driver Code
var
n = 10, k = 3;
candies(n, k);
// This code contributed by Rajput-Ji
</script>
Output:
5 2 3
Time complexity: O(Number of turns + K)
Auxiliary Space: O(k)
An efficient approach is to find the largest number(say MAXI) whose sum upto natural numbers is less than N using Binary search. Since the last number will always be a multiple of K, we get the last number of complete turns. Subtract the summation till then from N. Distribute the remaining candies by traversing in the array.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using
namespace
std;
// Function to find out the number of
// candies every person received
void
candies(
int
n,
int
k)
{
// Count number of complete turns
int
count = 0;
// Get the last term
int
ind = 1;
// Stores the number of candies
int
arr[k];
memset
(arr, 0,
sizeof
(arr));
int
low = 0, high = n;
// Do a binary search to find the number whose
// sum is less than N.
while
(low <= high) {
// Get mide
int
mid = (low + high) >> 1;
int
sum = (mid * (mid + 1)) >> 1;
// If sum is below N
if
(sum <= n) {
// Find number of complete turns
count = mid / k;
// Right halve
low = mid + 1;
}
else
{
// Left halve
high = mid - 1;
}
}
// Last term of last complete series
int
last = (count * k);
// Subtract the sum till
n -= (last * (last + 1)) / 2;
int
i = 0;
// First term of incomplete series
int
term = (count * k) + 1;
while
(n) {
if
(term <= n) {
arr[i++] = term;
n -= term;
term++;
}
else
{
arr[i] += n;
n = 0;
}
}
// Count the total candies
for
(
int
i = 0; i < k; i++)
arr[i] += (count * (i + 1))
+ (k * (count * (count - 1)) / 2);
// Print the total candies
for
(
int
i = 0; i < k; i++)
cout << arr[i] <<
" "
;
}
// Driver Code
int
main()
{
int
n = 7, k = 4;
candies(n, k);
return
0;
}
Java
// Java implementation of the above approach
class
GFG
{
// Function to find out the number of
// candies every person received
static
void
candies(
int
n,
int
k)
{
// Count number of complete turns
int
count =
0
;
// Get the last term
int
ind =
1
;
// Stores the number of candies
int
[]arr=
new
int
[k];
for
(
int
i=
0
;i<k;i++)
arr[i]=
0
;
int
low =
0
, high = n;
// Do a binary search to find the number whose
// sum is less than N.
while
(low <= high) {
// Get mide
int
mid = (low + high) >>
1
;
int
sum = (mid * (mid +
1
)) >>
1
;
// If sum is below N
if
(sum <= n) {
// Find number of complete turns
count = mid / k;
// Right halve
low = mid +
1
;
}
else
{
// Left halve
high = mid -
1
;
}
}
// Last term of last complete series
int
last = (count * k);
// Subtract the sum till
n -= (last * (last +
1
)) /
2
;
int
j =
0
;
// First term of incomplete series
int
term = (count * k) +
1
;
while
(n >
0
) {
if
(term <= n) {
arr[j++] = term;
n -= term;
term++;
}
else
{
arr[j] += n;
n =
0
;
}
}
// Count the total candies
for
(
int
i =
0
; i < k; i++)
arr[i] += (count * (i +
1
))
+ (k * (count * (count -
1
)) /
2
);
// Print the total candies
for
(
int
i =
0
; i < k; i++)
System.out.print( arr[i] +
" "
);
}
// Driver Code
public
static
void
main(String []args)
{
int
n =
7
, k =
4
;
candies(n, k);
}
}
// This code is contributed by ihritik
Python3
# Python3 implementation of the above approach
# Function to find out the number of
# candies every person received
def
candies(n, k):
# Count number of complete turns
count
=
0
;
# Get the last term
ind
=
1
;
# Stores the number of candies
arr
=
[
0
]
*
k;
low
=
0
;
high
=
n;
# Do a binary search to find the
# number whose sum is less than N.
while
(low <
=
high):
# Get mide
mid
=
(low
+
high) >>
1
;
sum
=
(mid
*
(mid
+
1
)) >>
1
;
# If sum is below N
if
(
sum
<
=
n):
# Find number of complete turns
count
=
int
(mid
/
k);
# Right halve
low
=
mid
+
1
;
else
:
# Left halve
high
=
mid
-
1
;
# Last term of last complete series
last
=
(count
*
k);
# Subtract the sum till
n
-
=
int
((last
*
(last
+
1
))
/
2
);
i
=
0
;
# First term of incomplete series
term
=
(count
*
k)
+
1
;
while
(n):
if
(term <
=
n):
arr[i]
=
term;
i
+
=
1
;
n
-
=
term;
term
+
=
1
;
else
:
arr[i]
+
=
n;
n
=
0
;
# Count the total candies
for
i
in
range
(k):
arr[i]
+
=
((count
*
(i
+
1
))
+
int
(k
*
(count
*
(count
-
1
))
/
2
));
# Print the total candies
for
i
in
range
(k):
print
(arr[i], end
=
" "
);
# Driver Code
n
=
7
;
k
=
4
;
candies(n, k);
# This code is contributed by chandan_jnu
C#
// C# implementation of the above approach
using
System;
class
GFG
{
// Function to find out the number of
// candies every person received
static
void
candies(
int
n,
int
k)
{
// Count number of complete turns
int
count = 0;
// Get the last term
int
ind = 1;
// Stores the number of candies
int
[]arr=
new
int
[k];
for
(
int
i=0;i<k;i++)
arr[i]=0;
int
low = 0, high = n;
// Do a binary search to find the number whose
// sum is less than N.
while
(low <= high) {
// Get mide
int
mid = (low + high) >> 1;
int
sum = (mid * (mid + 1)) >> 1;
// If sum is below N
if
(sum <= n) {
// Find number of complete turns
count = mid / k;
// Right halve
low = mid + 1;
}
else
{
// Left halve
high = mid - 1;
}
}
// Last term of last complete series
int
last = (count * k);
// Subtract the sum till
n -= (last * (last + 1)) / 2;
int
j = 0;
// First term of incomplete series
int
term = (count * k) + 1;
while
(n > 0) {
if
(term <= n) {
arr[j++] = term;
n -= term;
term++;
}
else
{
arr[j] += n;
n = 0;
}
}
// Count the total candies
for
(
int
i = 0; i < k; i++)
arr[i] += (count * (i + 1))
+ (k * (count * (count - 1)) / 2);
// Print the total candies
for
(
int
i = 0; i < k; i++)
Console.Write( arr[i] +
" "
);
}
// Driver Code
public
static
void
Main()
{
int
n = 7, k = 4;
candies(n, k);
}
}
// This code is contributed by ihritik
PHP
<?php
// PHP implementation of the above approach
// Function to find out the number of
// candies every person received
function
candies(
$n
,
$k
)
{
// Count number of complete turns
$count
= 0;
// Get the last term
$ind
= 1;
// Stores the number of candies
$arr
=
array_fill
(0,
$k
, 0);
$low
= 0;
$high
=
$n
;
// Do a binary search to find the
// number whose sum is less than N.
while
(
$low
<=
$high
)
{
// Get mide
$mid
= (
$low
+
$high
) >> 1;
$sum
= (
$mid
* (
$mid
+ 1)) >> 1;
// If sum is below N
if
(
$sum
<=
$n
)
{
// Find number of complete turns
$count
= (int)(
$mid
/
$k
);
// Right halve
$low
=
$mid
+ 1;
}
else
{
// Left halve
$high
=
$mid
- 1;
}
}
// Last term of last complete series
$last
= (
$count
*
$k
);
// Subtract the sum till
$n
-= (int)((
$last
* (
$last
+ 1)) / 2);
$i
= 0;
// First term of incomplete series
$term
= (
$count
*
$k
) + 1;
while
(
$n
)
{
if
(
$term
<=
$n
)
{
$arr
[
$i
++] =
$term
;
$n
-=
$term
;
$term
++;
}
else
{
$arr
[
$i
] +=
$n
;
$n
= 0;
}
}
// Count the total candies
for
(
$i
= 0;
$i
<
$k
;
$i
++)
$arr
[
$i
] += (
$count
* (
$i
+ 1)) +
(int)(
$k
* (
$count
* (
$count
- 1)) / 2);
// Print the total candies
for
(
$i
= 0;
$i
<
$k
;
$i
++)
echo
$arr
[
$i
] .
" "
;
}
// Driver Code
$n
= 7;
$k
= 4;
candies(
$n
,
$k
);
// This code is contributed
// by chandan_jnu
?>
Javascript
<script>
// javascript implementation of the above approach
// Function to find out the number of
// candies every person received
function
candies(n , k) {
// Count number of complete turns
var
count = 0;
// Get the last term
var
ind = 1;
// Stores the number of candies
var
arr = Array(k).fill(0);
for
(i = 0; i < k; i++)
arr[i] = 0;
var
low = 0, high = n;
// Do a binary search to find the number whose
// sum is less than N.
while
(low <= high) {
// Get mide
var
mid = parseInt((low + high) /2);
var
sum = parseInt((mid * (mid + 1)) / 2);
// If sum is below N
if
(sum <= n) {
// Find number of complete turns
count = parseInt(mid / k);
// Right halve
low = mid + 1;
}
else
{
// Left halve
high = mid - 1;
}
}
// Last term of last complete series
var
last = (count * k);
// Subtract the sum till
n -= (last * (last + 1)) / 2;
var
j = 0;
// First term of incomplete series
var
term = (count * k) + 1;
while
(n > 0) {
if
(term <= n) {
arr[j++] = term;
n -= term;
term++;
}
else
{
arr[j] += n;
n = 0;
}
}
// Count the total candies
for
(i = 0; i < k; i++)
arr[i] += (count * (i + 1)) + (k * (count * (count - 1)) / 2);
// Print the total candies
for
(i = 0; i < k; i++)
document.write(arr[i] +
" "
);
}
// Driver Code
var
n = 7, k = 4;
candies(n, k);
// This code contributed by aashish1995
</script>
Output:
1 2 3 1
Time Complexity: O(log N + K)
Auxiliary Space: O(K) for given K
Distribute N candies among K people in c++:
Approach:
The distribute_candies function takes two integers as input: N, which represents the total number of candies, and K, which represents the number of people. It returns a vector of integers, where the i-th element represents the number of candies distributed to the i-th person.
The function initializes a vector result of K elements with zero candies. It then loops until all N candies have been distributed. In each iteration, it calculates the number of candies to give to the current person (candies_to_give) as the minimum of N and i+1. It then adds candies_to_give to the number of candies distributed to the i-th person in result, and subtracts candies_to_give from N. Finally, it increments i to move to the next person.
C++
#include <iostream>
#include <vector>
std::vector<
int
> distribute_candies(
int
N,
int
K) {
std::vector<
int
> result(K, 0);
// initialize a vector of K elements with zero candies
int
i = 0;
while
(N > 0) {
// loop until we have no more candies to distribute
int
candies_to_give = std::min(N, i+1);
result[i % K] += candies_to_give;
// distribute candies to the i-th person
N -= candies_to_give;
// subtract the distributed candies from N
i += 1;
// move to the next person
}
return
result;
}
int
main() {
int
N = 10;
int
K = 3;
std::vector<
int
> result = distribute_candies(N, K);
for
(
int
i = 0; i < K; i++) {
std::cout << result[i] <<
" "
;
}
return
0;
}
Java
import
java.util.*;
public
class
DistributeCandies {
public
static
List<Integer> distributeCandies(
int
N,
int
K)
{
List<Integer> result
=
new
ArrayList<>(Collections.nCopies(
K,
0
));
// initialize a list of K elements
// with zero candies
int
i =
0
;
while
(N >
0
) {
// loop until we have no more
// candies to distribute
int
candiesToGive = Math.min(N, i +
1
);
result.set(
i % K,
result.get(i % K)
+ candiesToGive);
// distribute candies
// to the i-th person
N -= candiesToGive;
// subtract the distributed
// candies from N
i +=
1
;
// move to the next person
}
return
result;
}
public
static
void
main(String[] args)
{
int
N =
10
;
int
K =
3
;
List<Integer> result = distributeCandies(N, K);
for
(
int
i =
0
; i < K; i++) {
System.out.print(result.get(i) +
" "
);
}
}
}
Python3
def
distribute_candies(N, K):
result
=
[
0
]
*
K
# initialize a list of K elements with zero candies
i
=
0
while
N >
0
:
# loop until we have no more candies to distribute
candies_to_give
=
min
(N, i
+
1
)
result[i
%
K]
+
=
candies_to_give
# distribute candies to the i-th person
N
-
=
candies_to_give
# subtract the distributed candies from N
i
+
=
1
# move to the next person
return
result
if
__name__
=
=
'__main__'
:
N
=
10
K
=
3
result
=
distribute_candies(N, K)
for
i
in
range
(K):
print
(result[i], end
=
" "
)
# output: 3 3 4
C#
using
System;
using
System.Collections.Generic;
public
class
Gfg {
public
static
List<
int
> distribute_candies(
int
N,
int
K) {
List<
int
> result =
new
List<
int
>(
new
int
[K]);
// initialize a list of K elements with zero candies
int
i = 0;
while
(N > 0) {
// loop until we have no more candies to distribute
int
candies_to_give = Math.Min(N, i+1);
result[i % K] += candies_to_give;
// distribute candies to the i-th person
N -= candies_to_give;
// subtract the distributed candies from N
i += 1;
// move to the next person
}
return
result;
}
public
static
void
Main() {
int
N = 10;
int
K = 3;
List<
int
> result = distribute_candies(N, K);
for
(
int
i = 0; i < K; i++) {
Console.Write(result[i] +
" "
);
}
// output: 3 3 4
}
}
Javascript
// JavaScript equivalent
function
distribute_candies(N, K) {
let result = Array(K).fill(0);
// initialize a list of K elements with zero candies
let i = 0;
while
(N > 0) {
// loop until we have no more candies to distribute
let candies_to_give = Math.min(N, i+1);
result[i % K] += candies_to_give;
// distribute candies to the i-th person
N -= candies_to_give;
// subtract the distributed candies from N
i += 1;
// move to the next person
}
return
result;
}
let N = 10;
let K = 3;
let result = distribute_candies(N, K); temp=
""
;
for
(let i = 0; i < K; i++) {
temp = temp+result[i]+
" "
;
} console.log(temp);
Output
5 2 3
The time complexity of this algorithm is O(N), because we need to distribute each of the N candies.
The auxiliary space of this algorithm is O(K), because we use a vector of K elements to store the candies distributed to each person.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!