↓Skip to main content
  1. LeetCode/

LeetCode 1103: Distribute Candies to People

·1 min· ·
LeetCode Easy Math Simulation
Wei Yi Chung
Author
Wei Yi Chung
Working at the contributing of open source, distributed systems, and data engineering.
Table of Contents

Meta Data
#

Difficulty: easy First Attempt: 2022-10-18

  • Submissions: Wrong Answer ×3 → Accepted ×3

Approach
#

Simulate: turn i (from 0) gives person i % n min(i + 1, remaining) candies. There are only O(√candies) turns, since 1 + 2 + ... + k ≈ k² / 2.

My Attempts
#

The first three did gave += 1 before candies -= gave, subtracting the next turn’s amount and losing one candy each time: candies = 3 with one person should be [3]; they returned [2]. Swapping the two lines passed.

Solution
#

class Solution:
    def distributeCandies(self, candies: int, num_people: int) -> List[int]:
        res = [0] * num_people
        i = 0
        while candies > 0:
            give = min(i + 1, candies)
            res[i % num_people] += give
            candies -= give
            i += 1
        return res

Complexity
#

Time O(√candies + n), space O(n).

Mistakes to Avoid
#

  • Subtract this turn’s amount before incrementing the next one; reversing the order over-subtracts.

Interview Explanation
#

I simulate: turn i gives i + 1 candies to person i mod n, or everything left if that is less. There are about √candies turns.

Related

LeetCode 415: Add Strings
·2 mins
LeetCode Easy Math String Simulation
LeetCode 415 note: add digit by digit from the ends with two pointers, tracking the carry, and append any leftover carry after the loop
LeetCode 412: Fizz Buzz
·1 min
LeetCode Easy Math String Simulation
LeetCode 412 note: check multiples of 15 first, then 5 and 3; multiples need %, not //
LeetCode 258: Add Digits
·1 min
LeetCode Easy Math Simulation Number-Theory
LeetCode 258 note: sum the digits repeatedly until one remains; the O(1) answer is the digital root 1 + (n - 1) % 9
LeetCode 67: Add Binary
·2 mins
LeetCode Easy Math String Bit-Manipulation Simulation
LeetCode 67 note: add from the ends of both strings digit by digit, with carry sum // 2 and digit sum % 2
LeetCode 1137: N-th Tribonacci Number
·2 mins
LeetCode Easy Math Dynamic-Programming Memoization
LeetCode 1137 note: like Fibonacci, roll three variables; watch the base values T0 = 0, T1 = T2 = 1 and the loop range
LeetCode 1030: Matrix Cells in Distance Order
·2 mins
LeetCode Easy Array Math Geometry Sorting
LeetCode 1030 note: list every coordinate and sort by Manhattan distance to the center; return coordinates, not distances