Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Distribute Repeating Integers solution and explanation

HardArrayBacktrackingBit ManipulationBitmask7 min read41.1% acceptanceUpdated 9 Apr 2026
Asked atGoogle
Practise Distribute Repeating Integers
15:57
花花酱 LeetCode 1655. Distribute Repeating Integers - 刷题找工作 EP370Hua Hua · 15:57 · 2K viewsWatch on YouTube
6 more videos on this problem
  1. 花花酱 LeetCode 1655. Distribute Repeating Integers - 刷题找工作 EP370Hua Hua · 15:57 · 2K views
  2. LeetCode 1655. Distribute Repeating IntegersHappy Coding · 36:02 · 1K views
  3. 【每日一题】1655. Distribute Repeating Integers, 11/15/2020Huifeng Guan · 35:31 · 663 views
  4. 1655. Distribute Repeating Integers (Leetcode Hard)Programming Live with Larry · 27:37 · 622 views
  5. Day 21/75: Problem Name: Distribute Repeating Integers | Leetcode | #75DaysHardLCCodeInsanity · 15:06 · 368 views
  6. LeetCode 1655: Distribute Repeating IntegersAlitaCode · 32:20 · 11 views
  7. ข้อ 1655. Distribute Repeating Integers | LeetCodeThakorn Jareonrat · 11:50 · 7 views

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. Determine if it is possible to distribute nums such that:

  • The ith customer gets exactly quantity[i] integers,
  • The integers the ith customer gets are all equal, and
  • Every customer is satisfied.

Return true if it is possible to distribute nums according to the above conditions.

Example 1:

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

Example 2:

Input: nums = [1,2,3,3], quantity = [2]
Output: true
Explanation: The 0th customer is given [3,3]. The integers [1,2] are not used.

Example 3:

Input: nums = [1,1,2,2], quantity = [2,2]
Output: true
Explanation: The 0th customer is given [1,1], and the 1st customer is given [2,2].

Constraints:

  • n == nums.length
  • 1 <= n <= 105
  • 1 <= nums[i] <= 1000
  • m == quantity.length
  • 1 <= m <= 10
  • 1 <= quantity[i] <= 105
  • There are at most 50 unique values in nums.

Approach overview

Problem Overview: You receive an array of integers where values may repeat, and a list of customer quantity requests. Each customer must receive exactly the number of integers they request, and all integers given to a customer must have the same value. The task is to determine whether the available frequencies of numbers can satisfy every request.

Approach 1: Backtracking with Frequency Matching (Exponential, practical for small m)

First count the frequency of each number using a hash map or frequency array from the array. Customers only care about counts, not actual values. Sort the request quantities in descending order so larger demands are handled first, which prunes failing branches earlier. During recursion, try assigning each request to any remaining frequency bucket that can satisfy it, subtract the quantity, recurse, and backtrack if it fails. This search explores possible assignments of requests to value frequencies. Time complexity is roughly O(k^m) in the worst case (k unique numbers, m customers), with O(k) space for recursion and frequency tracking.

Approach 2: Bitmask Dynamic Programming (O(n * 2^m * m))

Dynamic programming improves the brute-force search by grouping customer assignments using a bitmask. Let m be the number of customers. Precompute the total quantity required for every subset of customers represented by a bitmask. Then iterate through each number frequency and decide which subset of customers it can satisfy. The DP state dp[i][mask] means whether the first i frequencies can fulfill the set of customers represented by mask. For each state, try assigning a submask of remaining customers whose total demand does not exceed the current frequency. This converts many repeated backtracking checks into cached transitions. Time complexity is O(n * 2^m * m) and space complexity is O(n * 2^m), where n is the number of unique values. This approach relies heavily on dynamic programming and subset enumeration.

Recommended for interviews: The backtracking solution usually comes first in interviews because it directly models assigning requests to available frequencies. Sorting requests and pruning branches shows strong problem-solving instincts. The bitmask DP approach demonstrates deeper optimization skills and knowledge of subset DP, which interviewers often expect for Hard problems with small constraint sizes.

Approach 1: Backtracking Approach

In this approach, use a backtracking algorithm to attempt assigning quantities to customers. You'll iterate over each unique integer and attempt to fulfill as many customer orders as possible with that integer's frequency. If any assignment fails, backtrack and try a different distribution.

from collections import Counter

def canDistribute(nums, quantity):
    def backtrack(i):
        if i == len(quantity):
            return True
        for num in unique_vals:
            if freq[num] >= quantity[i]:
                freq[num] -= quantity[i]
                if backtrack(i+1):
                    return True
                freq[num] += quantity[i]
        return False
    freq = Counter(nums)
    unique_vals = list(freq.keys())
    quantity.sort(reverse=True)  # Sorting may help prune the search space
    return backtrack(0)
#include <vector>
#include <unordered_map>
#include <algorithm>

bool backtrack(std::vector<int>& quantity, std::unordered_map<int, int>& freq, size_t i) {
    if (i == quantity.size()) return true;
    for (auto& [num, count] : freq) {
        if (count >= quantity[i]) {
            count -= quantity[i];
            if (backtrack(quantity, freq, i + 1)) return true;
            count += quantity[i];
        }
    }
    return false;
}

bool canDistribute(std::vector<int>& nums, std::vector<int>& quantity) {
    std::unordered_map<int, int> freq;
    for (int num : nums) freq[num]++;
    std::sort(quantity.rbegin(), quantity.rend());
    return backtrack(quantity, freq, 0);
}

This Python solution initializes a frequency counter for each unique integer in nums. It defines a recursive backtrack function to try fitting each customer's quantity using any available number's frequency. Frequency is reduced when a fit is attempted and restored on failure to explore other possibilities.

Complexity

Time Complexity: O(m * 50^m), where 'm' is the number of orders and '50' is the maximum number of unique integers. In the worst case, we try all combinations of orders.
Space Complexity: O(50 + m) due to the recursive stack and frequency counter.

Try this approach in the editor

Approach 2: Dynamic Programming Approach

Leveraging dynamic programming, create a state representation for each combination of orders to minimize and accurately track required integers. Use a bitmask for denoting which customer orders have been completed and update the algorithm’s state as combinations are validly formed.

function canDistribute(nums, quantity) {
    const freq = {};
    nums.forEach(num => { freq[num] = (freq[num] || 0) + 1; });
    quantity.sort((a, b) => b - a);
    const dp = Array(1 << quantity.length).fill(Infinity);
    dp[0] = 0;

    for (let mask = 0; mask < (1 << quantity.length); ++mask) {
        if (dp[mask] === Infinity) continue;
        for (let num of Object.keys(freq)) {
            if (freq[num] > 0) {
                let newMask = mask;
                let used = 0;
                for (let i = 0; i < quantity.length; ++i) {
                    if ((mask & (1 << i)) === 0 && freq[num] >= quantity[i] + used) {
                        newMask |= (1 << i);
                        used += quantity[i];
                    }
                }
                dp[newMask] = Math.min(dp[newMask], dp[mask] + 1);
            }
        }
    }
    return dp[(1 << quantity.length) - 1] != Infinity;
}

This JavaScript solution populates a dynamic programming table where each state is a bitmask representing complete status of customer orders. For each number, possible matches are tested, updating the DP table with new states as they reach a valid completion threshold.

Complexity

Time Complexity: O(50 * 2^m), as we evaluate possible states over order combinations.
Space Complexity: O(2^m), for DP table storage.

Try this approach in the editor

Approach 3: State Compression Dynamic Programming + Subset Enumeration

First, we count the occurrence of each number in the array nums, and record it in the hash table cnt. Then we store the values in the hash table into the array arr. We denote the length of the array arr as n.

Note that the length of the array quantity does not exceed 10, so we can use a binary number to represent a subset of quantity. That is, the number j represents a subset of quantity, where the i-th bit of the binary representation of j is 1 means the i-th number in quantity is selected, and 0 means the i-th number is not selected.

We can preprocess an array s, where s[j] represents the sum of all numbers in the subset j of quantity.

Next, we define f[i][j] to represent whether the numbers in arr[0,..i-1] can be successfully allocated to the subset j of quantity, where i ranges from [0,..n-1], and j ranges from [0,2^m-1], where m is the length of quantity.

Considering f[i][j], if there exists a subset k in j such that s[k] <= arr[i], and f[i-1][j XOR k] is true, then f[i][j] is true, otherwise f[i][j] is false.

The answer is f[n-1][2^m-1].

The time complexity is O(n * 3^m), and the space complexity is O(n * 2^m). Here, n is the number of different integers in the array nums, and m is the length of the array quantity.

class Solution {
    public boolean canDistribute(int[] nums, int[] quantity) {
        int m = quantity.length;
        int[] s = new int[1 << m];
        for (int i = 1; i < 1 << m; ++i) {
            for (int j = 0; j < m; ++j) {
                if ((i >> j & 1) != 0) {
                    s[i] = s[i ^ (1 << j)] + quantity[j];
                    break;
                }
            }
        }
        Map<Integer, Integer> cnt = new HashMap<>(50);
        for (int x : nums) {
            cnt.merge(x, 1, Integer::sum);
        }
        int n = cnt.size();
        int[] arr = new int[n];
        int i = 0;
        for (int x : cnt.values()) {
            arr[i++] = x;
        }
        boolean[][] f = new boolean[n][1 << m];
        for (i = 0; i < n; ++i) {
            f[i][0] = true;
        }
        for (i = 0; i < n; ++i) {
            for (int j = 1; j < 1 << m; ++j) {
                if (i > 0 && f[i - 1][j]) {
                    f[i][j] = true;
                    continue;
                }
                for (int k = j; k > 0; k = (k - 1) & j) {
                    boolean ok1 = i == 0 ? j == k : f[i - 1][j ^ k];
                    boolean ok2 = s[k] <= arr[i];
                    if (ok1 && ok2) {
                        f[i][j] = true;
                        break;
                    }
                }
            }
        }
        return f[n - 1][(1 << m) - 1];
    }
}
function canDistribute(nums: number[], quantity: number[]): boolean {
    const m = quantity.length;
    const s: number[] = new Array(1 << m).fill(0);
    for (let i = 1; i < 1 << m; ++i) {
        for (let j = 0; j < m; ++j) {
            if ((i >> j) & 1) {
                s[i] = s[i ^ (1 << j)] + quantity[j];
                break;
            }
        }
    }
    const cnt: Map<number, number> = new Map();
    for (const x of nums) {
        cnt.set(x, (cnt.get(x) || 0) + 1);
    }
    const n = cnt.size;
    const arr: number[] = [];
    for (const [_, v] of cnt) {
        arr.push(v);
    }
    const f: boolean[][] = new Array(n).fill(false).map(() => new Array(1 << m).fill(false));
    for (let i = 0; i < n; ++i) {
        f[i][0] = true;
    }
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < 1 << m; ++j) {
            if (i > 0 && f[i - 1][j]) {
                f[i][j] = true;
                continue;
            }
            for (let k = j; k > 0; k = (k - 1) & j) {
                const ok1: boolean = (i == 0 && j == k) || (i > 0 && f[i - 1][j ^ k]);
                const ok2: boolean = s[k] <= arr[i];
                if (ok1 && ok2) {
                    f[i][j] = true;
                    break;
                }
            }
        }
    }
    return f[n - 1][(1 << m) - 1];
}
func canDistribute(nums []int, quantity []int) bool {
	m := len(quantity)
	s := make([]int, 1<<m)
	for i := 1; i < 1<<m; i++ {
		for j := 0; j < m; j++ {
			if i>>j&1 == 1 {
				s[i] = s[i^(1<<j)] + quantity[j]
				break
			}
		}
	}
	cnt := map[int]int{}
	for _, x := range nums {
		cnt[x]++
	}
	n := len(cnt)
	arr := make([]int, 0, n)
	for _, x := range cnt {
		arr = append(arr, x)
	}
	f := make([][]bool, n)
	for i := range f {
		f[i] = make([]bool, 1<<m)
		f[i][0] = true
	}
	for i := 0; i < n; i++ {
		for j := 0; j < 1<<m; j++ {
			if i > 0 && f[i-1][j] {
				f[i][j] = true
				continue
			}
			for k := j; k > 0; k = (k - 1) & j {
				ok1 := (i == 0 && j == k) || (i > 0 && f[i-1][j-k])
				ok2 := s[k] <= arr[i]
				if ok1 && ok2 {
					f[i][j] = true
					break
				}
			}
		}
	}
	return f[n-1][(1<<m)-1]
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Backtracking Approach

Time Complexity: O(m * 50^m), where 'm' is the number of orders and '50' is the maximum number of unique integers. In the worst case, we try all combinations of orders.
Space Complexity: O(50 + m) due to the recursive stack and frequency counter.

Dynamic Programming Approach

Time Complexity: O(50 * 2^m), as we evaluate possible states over order combinations.
Space Complexity: O(2^m), for DP table storage.

State Compression Dynamic Programming + Subset Enumeration–

Complexity analysis

ApproachTimeSpaceWhen to Use
Backtracking with Frequency MatchingO(k^m) worst caseO(k)When the number of customers is small and pruning with sorted requests is effective
Bitmask Dynamic ProgrammingO(n * 2^m * m)O(n * 2^m)General optimized solution when customers ≤ 10 and subset DP is feasible

Frequently asked questions

Is Distribute Repeating Integers easy or hard?

Distribute Repeating Integers is classified as a Hard problem on LeetCode with an acceptance rate around 40%. The challenge comes from modeling the assignment of requests to frequency buckets and optimizing the search using pruning or subset dynamic programming.

Distribute Repeating Integers Python/Java solution

Python and C++ implementations typically use recursive backtracking with sorted request arrays and frequency counts. JavaScript implementations often use bitmask dynamic programming where dp[i][mask] tracks whether the first i frequencies can satisfy a subset of customers.

How to solve Distribute Repeating Integers in O(n)?

An O(n) solution is not possible because the problem requires exploring combinations of customer requests. The practical optimal method uses bitmask dynamic programming over customer subsets with complexity O(n * 2^m * m), which is efficient since m is usually ≤ 10.

What is the best approach for Distribute Repeating Integers?

The most reliable approach uses bitmask dynamic programming. Precompute the demand of every subset of customers and assign those subsets to number frequencies. This reduces repeated exploration compared to naive recursion and runs in O(n * 2^m * m) time where m is the number of customers.

Is Distribute Repeating Integers asked at Google/Amazon/Meta?

Problems involving frequency distribution, subset assignment, and bitmask DP frequently appear in interviews at companies like Google, Amazon, and Meta. This problem tests backtracking optimization and subset dynamic programming, both common patterns in senior-level interview rounds.

What data structure is used in Distribute Repeating Integers?

The solution relies on frequency maps or arrays to count occurrences of each integer, combined with bitmasks to represent subsets of customers. Dynamic programming tables or recursive backtracking stacks track which requests have been satisfied.

What is the time complexity of Distribute Repeating Integers?

The optimized bitmask DP solution runs in O(n * 2^m * m) time and O(n * 2^m) space, where n is the number of unique integer values and m is the number of customers. A simpler backtracking approach can degrade to roughly O(k^m) in the worst case but works well with pruning when m is small.

Comments

Now write it yourselfClose this page and solve Distribute Repeating Integers in the editor, without looking.
Practise Distribute Repeating Integers