How hard is LeetCode 1655. Distribute Repeating Integers?

LeetCode 1655. Distribute Repeating Integers is rated Hard on LeetCode.

What is the time complexity of LeetCode 1655. Distribute Repeating Integers?

The Python solution on this page runs in `O(n * 3^m)`.

What is the space complexity of LeetCode 1655. Distribute Repeating Integers?

The Python solution on this page uses `O(n * 2^m)` auxiliary space.

What topics does LeetCode 1655. Distribute Repeating Integers cover?

LeetCode 1655. Distribute Repeating Integers is tagged Bit Manipulation, Array, Dynamic Programming, Backtracking and Bitmask on LeetCode.

Distribute Repeating Integers — LeetCode 1655 Python Solution

HardBit ManipulationArrayDynamic ProgrammingBacktrackingBitmask

Problem: #1655
Pattern: Backtracking
Reading time: 5 min
Source: leetcode.com

The problem

You are given an array of n integers, nums, where there are at most 50 unique values in the array. You are also given an array of m customer order quantities, quantity, where quantity[i] is the amount of integers the ith customer ordered.

Example

Input: nums = [1,2,3,4], quantity = [2]
Output: false
Explanation: The 0th customer cannot be given two different integers.

Python solution

Python

class Solution:
    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:
        m = len(quantity)
        s = [0] * (1 << m)
        for i in range(1, 1 << m):
            for j in range(m):
                if i >> j & 1:
                    s[i] = s[i ^ (1 << j)] + quantity[j]
                    break
        cnt = Counter(nums)
        arr = list(cnt.values())
        n = len(arr)
        f = [[False] * (1 << m) for _ in range(n)]
        for i in range(n):
            f[i][0] = True
        for i, x in enumerate(arr):
            for j in range(1, 1 << m):
                if i and f[i - 1][j]:
                    f[i][j] = True
                    continue
                k = j
                while k:
                    ok1 = j == k if i == 0 else f[i - 1][j ^ k]
                    ok2 = s[k] <= x
                    if ok1 and ok2:
                        f[i][j] = True
                        break
                    k = (k - 1) & j
        return f[-1][-1]

Complexity

Measure	Complexity
Time	`O(n * 3^m)`
Space	`O(n * 2^m)` auxiliary

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 1655. Distribute Repeating Integers is filed here because LeetCode tags it Backtracking, which is the vocabulary this hub collects.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1655. Distribute Repeating Integers?: LeetCode 1655. Distribute Repeating Integers is rated Hard on LeetCode.
What is the time complexity of LeetCode 1655. Distribute Repeating Integers?: The Python solution on this page runs in `O(n * 3^m)`.
What is the space complexity of LeetCode 1655. Distribute Repeating Integers?: The Python solution on this page uses `O(n * 2^m)` auxiliary space.
What topics does LeetCode 1655. Distribute Repeating Integers cover?: LeetCode 1655. Distribute Repeating Integers is tagged Bit Manipulation, Array, Dynamic Programming, Backtracking and Bitmask on LeetCode.