1103.DistributeCandiesToPeople.cpp

/*
 * @lc app=leetcode id=1103 lang=cpp
 *
 * [1103] Distribute Candies to People
 *
 * https://leetcode.com/problems/distribute-candies-to-people/description/
 *
 * algorithms
 * Easy (60.57%)
 * Likes:    363
 * Dislikes: 93
 * Total Accepted:    41.8K
 * Total Submissions: 66K
 * Testcase Example:  '7\n4'
 *
 * We distribute some number of candies, to a row of n = num_people people in
 * the following way:
 * 
 * We then give 1 candy to the first person, 2 candies to the second person,
 * and so on until we give n candies to the last person.
 * 
 * Then, we go back to the start of the row, giving n + 1 candies to the first
 * person, n + 2 candies to the second person, and so on until we give 2 * n
 * candies to the last person.
 * 
 * This process repeats (with us giving one more candy each time, and moving to
 * the start of the row after we reach the end) until we run out of candies.
 * The last person will receive all of our remaining candies (not necessarily
 * one more than the previous gift).
 * 
 * Return an array (of length num_people and sum candies) that represents the
 * final distribution of candies.
 * 
 * 
 * Example 1:
 * 
 * 
 * Input: candies = 7, num_people = 4
 * Output: [1,2,3,1]
 * Explanation:
 * On the first turn, ans[0] += 1, and the array is [1,0,0,0].
 * On the second turn, ans[1] += 2, and the array is [1,2,0,0].
 * On the third turn, ans[2] += 3, and the array is [1,2,3,0].
 * On the fourth turn, ans[3] += 1 (because there is only one candy left), and
 * the final array is [1,2,3,1].
 * 
 * 
 * Example 2:
 * 
 * 
 * Input: candies = 10, num_people = 3
 * Output: [5,2,3]
 * Explanation: 
 * On the first turn, ans[0] += 1, and the array is [1,0,0].
 * On the second turn, ans[1] += 2, and the array is [1,2,0].
 * On the third turn, ans[2] += 3, and the array is [1,2,3].
 * On the fourth turn, ans[0] += 4, and the final array is [5,2,3].
 * 
 * 
 * 
 * Constraints:
 * 
 * 
 * 1 <= candies <= 10^9
 * 1 <= num_people <= 1000
 * 
 * 
 */

// @lc code=start
#include <vector>
#include<bits/stdc++.h>

class Solution {
public:
    std::vector<int> distributeCandies(int candies, int num_people) {
        
        std::vector<int> result(num_people, 0);
        
        int n_steps = sqrt(2 * candies);
        if ( (1 + n_steps) * n_steps / 2 > candies) {
            n_steps--;
        }
        
        for (int i = 0; i < num_people; i++) {
            int turns = n_steps / num_people + (i < n_steps % num_people);
            
            result[i] += (i + 1 + (turns - 1) * num_people + i + 1) * turns / 2;
            candies -= result[i];
        }
        
        result[n_steps % num_people] += candies;
        
        return result;
        
    }
};
// @lc code=end