Dado N dulces y K personas. En el primer turno, la primera persona recibe 1 caramelo, la segunda recibe 2 caramelos, y así sucesivamente hasta llegar a K personas. En el siguiente turno, la primera persona recibe K+1 caramelos, la segunda persona recibe k+2 caramelos, y así sucesivamente. Si la cantidad de dulces es menor que la cantidad requerida de dulces en cada turno, entonces la persona recibe la cantidad restante de dulces.
La tarea es encontrar el número total de dulces que cada persona tiene al final.
Ejemplos:
Entrada: N = 7, K = 4
Salida: 1 2 3 1
En el primer turno, a la cuarta persona se le deben dar 4 dulces, pero
solo queda 1, por lo que solo toma uno.
Entrada: N = 10, K = 3
Salida: 5 2 3
En el segundo turno primero recibe 4 y luego no nos quedan más caramelos.
Un enfoque ingenuo es iterar para cada turno y distribuir los dulces en consecuencia hasta que se terminen los dulces.
Complejidad del tiempo: O(Número de distribuciones)
Un mejor enfoque es realizar cada vuelta en O(1) calculando la suma de los números naturales hasta el último término de la serie que será (vueltas*k) y restando la suma de los números naturales hasta el último término de la serie anterior que es (turns-1)*k. Siga haciendo esto hasta que la suma sea menor que N, una vez que exceda, distribuya los dulces de la manera dada hasta que sea posible. Llamamos a un turno completado si cada persona obtiene la cantidad deseada de dulces que debe obtener en un turno.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
5 2 3
Complejidad del tiempo: O (Número de vueltas + K)
Espacio auxiliar: O(k)
Un enfoque eficiente es encontrar el número más grande (por ejemplo, MAXI) cuya suma de números naturales sea menor que N mediante la búsqueda binaria. Dado que el último número siempre será un múltiplo de K, obtenemos el último número de vueltas completas. Reste la suma hasta entonces de N. Distribuya los dulces restantes atravesando la array.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
1 2 3 1
Complejidad de tiempo: O (log N + K)