Skip to content

Inclusion Exclusion Principle

Table of Contents

2652. Sum Multiples

878. Nth Magical Number

1201. Ugly Number III

2928. Distribute Candies Among Children I

def distributeCandies(n: int, limit: int) -> int:
    def c2(n: int) -> int:
        return n * (n - 1) // 2 if n > 1 else 0

    return (
        c2(n + 2)
        - 3 * c2(n - limit + 1)
        + 3 * c2(n - 2 * limit)
        - c2(n - 3 * limit - 1)
    )


if __name__ == "__main__":
    assert distributeCandies(5, 2) == 3
    assert distributeCandies(3, 3) == 10

2929. Distribute Candies Among Children II

def distributeCandies(n: int, limit: int) -> int:
    def c2(n: int) -> int:
        return n * (n - 1) // 2 if n > 1 else 0

    return (
        c2(n + 2)
        - 3 * c2(n - limit + 1)
        + 3 * c2(n - 2 * limit)
        - c2(n - 3 * limit - 1)
    )


if __name__ == "__main__":
    assert distributeCandies(5, 2) == 3
    assert distributeCandies(3, 3) == 10

2930. Number of Strings Which Can Be Rearranged to Contain Substring

2513. Minimize the Maximum of Two Arrays

3116. Kth Smallest Amount With Single Denomination Combination

3130. Find All Possible Stable Binary Arrays II

3336. Find the Number of Subsequences With Equal GCD

2927. Distribute Candies Among Children III

def distributeCandies(n: int, limit: int) -> int:
    def c2(n: int) -> int:
        return n * (n - 1) // 2 if n > 1 else 0

    return (
        c2(n + 2)
        - 3 * c2(n - limit + 1)
        + 3 * c2(n - 2 * limit)
        - c2(n - 3 * limit - 1)
    )


if __name__ == "__main__":
    assert distributeCandies(5, 2) == 3
    assert distributeCandies(3, 3) == 10

Comments