Distribute Repeating Integers - Practice Coding Problems

Distribute Repeating Integers - 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 i-th customer ordered.

Determine if it is possible to distribute nums such that:

The i-th customer gets exactly quantity[i] integers
The integers the i-th customer gets are all equal
Every customer is satisfied

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

Input & Output

Example 1 — Basic Distribution

$ Input: nums = [1,2,3,4], quantity = [2]

› Output: false

💡 Note: No single value appears twice. Customer wants 2 identical items but max frequency is 1.

Example 2 — Successful Distribution

$ Input: nums = [1,2,3,3], quantity = [2]

› Output: true

💡 Note: Value 3 appears twice. Customer gets [3,3] which satisfies quantity = 2.

Example 3 — Multiple Customers

$ Input: nums = [1,1,2,2], quantity = [2,2]

› Output: true

💡 Note: Customer 0 gets [1,1], Customer 1 gets [2,2]. Both satisfied with identical items.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Count frequency of each unique number in the array

Assignment Process

Try to assign item types to customers based on their quantity needs

Validation

Check if all customers can be satisfied with identical items

Key Takeaway

🎯 Key Insight: Group identical items by frequency, then use backtracking or bitmask DP to find valid customer assignments

Asked in

a Amazon 45 G Google 32 M Microsoft 28 f Facebook 21

The key insight is to group identical numbers by frequency and use backtracking to assign item types to customers. Best approach is bitmask DP for small customer counts or optimized backtracking for general cases. Time: O(k × 3^m), Space: O(2^m)

Common Approaches

Approach	Time	Space	Notes
✓ Bitmask Dynamic Programming	O(k × 3^m)	O(2^m)	Use bitmask to represent customer subsets and memoize results for optimal performance
Brute Force Backtracking	O(k^m)	O(m)	Try all possible assignments of item types to customers using recursive backtracking
Optimized Backtracking with Pruning	O(k^m)	O(m)	Enhanced backtracking with sorting and early pruning for better performance

Bitmask Dynamic Programming — Algorithm Steps

Count frequency of each unique number
For each unique number, precompute all customer subsets it can satisfy
Use bitmask DP where state represents which customers are satisfied
Try all possible ways to satisfy remaining customers

Visualization

Tap to expand

Step-by-Step Walkthrough

Precompute Subsets

For each item frequency, find all customer combinations it can satisfy

Bitmask States

Use bits to represent which customers are satisfied

DP Transition

Combine states to build complete solution

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(int* nums, int numsSize, int* quantity, int quantitySize) {
    // Simple frequency counting
    int freqMap[1001] = {0};
    int minVal = nums[0], maxVal = nums[0];
    
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] < minVal) minVal = nums[i];
        if (nums[i] > maxVal) maxVal = nums[i];
    }
    
    for (int i = 0; i < numsSize; i++) {
        freqMap[nums[i] - minVal]++;
    }
    
    int freq[50];
    int freqSize = 0;
    for (int i = 0; i <= maxVal - minVal; i++) {
        if (freqMap[i] > 0) {
            freq[freqSize++] = freqMap[i];
        }
    }
    
    int m = quantitySize;
    
    // Precompute customer subsets each frequency can satisfy
    int canSatisfy[50][1024]; // [freq_idx][subset_idx] = mask
    int canSatisfySize[50] = {0};
    
    for (int i = 0; i < freqSize; i++) {
        for (int mask = 1; mask < (1 << m); mask++) {
            int total = 0;
            for (int j = 0; j < m; j++) {
                if (mask & (1 << j)) {
                    total += quantity[j];
                }
            }
            
            if (total <= freq[i]) {
                canSatisfy[i][canSatisfySize[i]++] = mask;
            }
        }
    }
    
    // DP with bitmask
    bool dp[1024] = {false};
    dp[0] = true;
    
    for (int i = 0; i < freqSize; i++) {
        for (int mask = (1 << m) - 1; mask >= 0; mask--) {
            if (!dp[mask]) continue;
            
            for (int j = 0; j < canSatisfySize[i]; j++) {
                int subset = canSatisfy[i][j];
                if ((mask & subset) == 0) {
                    dp[mask | subset] = true;
                }
            }
        }
    }
    
    return dp[(1 << m) - 1];
}

int main() {
    int nums[10000], quantity[50];
    int numsSize = 0, quantitySize = 0;
    
    char c;
    int num = 0;
    bool inNumber = false;
    
    while ((c = getchar()) != '\n') {
        if (c >= '0' && c <= '9') {
            num = num * 10 + (c - '0');
            inNumber = true;
        } else if (c == ',' || c == ']') {
            if (inNumber) {
                nums[numsSize++] = num;
                num = 0;
                inNumber = false;
            }
        }
    }
    
    num = 0;
    inNumber = false;
    while ((c = getchar()) != '\n' && c != EOF) {
        if (c >= '0' && c <= '9') {
            num = num * 10 + (c - '0');
            inNumber = true;
        } else if (c == ',' || c == ']') {
            if (inNumber) {
                quantity[quantitySize++] = num;
                num = 0;
                inNumber = false;
            }
        }
    }
    
    bool result = solution(nums, numsSize, quantity, quantitySize);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k × 3^m)

For k unique numbers, iterate through all subsets of m customers, 3^m comes from subset enumeration

✓ Linear Growth

Space Complexity

O(2^m)

DP array stores result for each possible customer combination bitmask

✓ Linear Space

23.4K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bitmask Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler