Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1655.html
1655. Distribute Repeating Integers
Level
Hard
Description
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 exactlyquantity[i]
integers, - The integers the
i-th
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].
Example 4:
Input: nums = [1,1,2,3], quantity = [2,2]
Output: false
Explanation: Although the 0th customer could be given [1,1], the 1st customer cannot be satisfied.
Example 5:
Input: nums = [1,1,1,1,1], quantity = [2,3]
Output: true
Explanation: The 0th customer is given [1,1], and the 1st customer is given [1,1,1].
Constraints:
n == nums.length
1 <= n <= 10^5
1 <= nums[i] <= 1000
m == quantity.length
1 <= m <= 10
1 <= quantity[i] <= 10^5
- There are at most
50
unique values innums
.
Solution
First, use a map to store all numbers’ occurrences in nums
. Then sort quantity
, and do backtrack using the map and quantity
, from the last element of quantity
.
During the backtrack, if an entry’s value is greater than or equal to the current value of quantity
, then try to distribute the integers to a customer, and continue the process for the next customer. If all customers are satisfied, return true
. If there is no way to make all customers satisfied, return false
.
-
class Solution { public boolean canDistribute(int[] nums, int[] quantity) { int sum = 0; for (int num : quantity) sum += num; if (sum > nums.length) return false; Map<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int num : nums) { int count = map.getOrDefault(num, 0) + 1; map.put(num, count); } Arrays.sort(quantity); return backtrack(map, quantity, quantity.length - 1); } public boolean backtrack(Map<Integer, Integer> map, int[] quantity, int index) { if (index == -1) return true; boolean flag = false; int curQuantity = quantity[index]; Set<Integer> keySet = map.keySet(); for (int key : keySet) { int value = map.get(key); if (value >= curQuantity) { map.put(key, value - curQuantity); flag = backtrack(map, quantity, index - 1); if (flag) break; else map.put(key, value); } } return flag; } }
-
class Solution { public: bool canDistribute(vector<int>& nums, vector<int>& quantity) { int m = quantity.size(); int s[1 << m]; memset(s, 0, sizeof(s)); for (int i = 1; i < 1 << m; ++i) { for (int j = 0; j < m; ++j) { if (i >> j & 1) { s[i] = s[i ^ (1 << j)] + quantity[j]; break; } } } unordered_map<int, int> cnt; for (int& x : nums) { ++cnt[x]; } int n = cnt.size(); vector<int> arr; for (auto& [_, x] : cnt) { arr.push_back(x); } bool f[n][1 << m]; memset(f, 0, sizeof(f)); for (int i = 0; i < n; ++i) { f[i][0] = true; } for (int i = 0; i < n; ++i) { for (int j = 1; j < 1 << m; ++j) { if (i && f[i - 1][j]) { f[i][j] = true; continue; } for (int k = j; k; k = (k - 1) & j) { bool ok1 = i == 0 ? j == k : f[i - 1][j ^ k]; bool ok2 = s[k] <= arr[i]; if (ok1 && ok2) { f[i][j] = true; break; } } } } return f[n - 1][(1 << m) - 1]; } };
-
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]
-
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] }
-
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]; }