Distribute N candies among K people | C ++ implementation of the above approach ; Function to find out the number of candies every person received ; Count number of complete turns ; Get the last term ; Stores the number of candies ; Do a binary search to find the number whose sum is less than N . ; Get mide ; If sum is below N ; Find number of complete turns ; Right halve ; Left halve ; Last term of last complete series ; Subtract the sum till ; First term of incomplete series ; Count the total candies ; Print the total candies ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void candies ( int n , int k ) { int count = 0 ; int ind = 1 ; int arr [ k ] ; memset ( arr , 0 , sizeof ( arr ) ) ; int low = 0 , high = n ; while ( low <= high ) { int mid = ( low + high ) >> 1 ; int sum = ( mid * ( mid + 1 ) ) >> 1 ; if ( sum <= n ) { count = mid / k ; low = mid + 1 ; } else { high = mid - 1 ; } } int last = ( count * k ) ; n -= ( last * ( last + 1 ) ) / 2 ; int i = 0 ; int term = ( count * k ) + 1 ; while ( n ) { if ( term <= n ) { arr [ i ++ ] = term ; n -= term ; term ++ ; } else { arr [ i ] += n ; n = 0 ; } } for ( int i = 0 ; i < k ; i ++ ) arr [ i ] += ( count * ( i + 1 ) ) + ( k * ( count * ( count - 1 ) ) / 2 ) ; for ( int i = 0 ; i < k ; i ++ ) cout << arr [ i ] << " ▁ " ; } int main ( ) { int n = 7 , k = 4 ; candies ( n , k ) ; return 0 ; }