1655. Distribute Repeating Integers LeetCode Solution
In this guide, you will get 1655. Distribute Repeating Integers LeetCode Solution with the best time and space complexity. The solution to Distribute Repeating Integers problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Distribute Repeating Integers solution in C++
- Distribute Repeating Integers solution in Java
- Distribute Repeating Integers solution in Python
- Additional Resources
Problem Statement of Distribute Repeating Integers
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.
Complexity Analysis
- Time Complexity: O(50 \cdot 3^m)
- Space Complexity: O(50 \cdot 2^m)
1655. Distribute Repeating Integers LeetCode Solution in C++
class Solution {
public:
bool canDistribute(vector<int>& nums, vector<int>& quantity) {
// validDistribution[i][j] := true if it's possible to distribute the i-th
// freq into a subset of quantity represented by the bitmask j
const vector<int> freqs = getFreqs(nums);
const vector<vector<bool>> validDistribution =
getValidDistribuition(freqs, quantity);
const int n = freqs.size();
const int m = quantity.size();
const int maxMask = 1 << m;
// dp[i][j] := true if it's possible to distribute freqs[i..n), where j is
// the bitmask of the selected quantity
vector<vector<bool>> dp(n + 1, vector<bool>(maxMask));
dp[n][maxMask - 1] = true;
for (int i = n - 1; i >= 0; --i)
for (int mask = 0; mask < maxMask; ++mask) {
dp[i][mask] = dp[i + 1][mask];
const int availableMask = ~mask & (maxMask - 1);
for (int submask = availableMask; submask > 0;
submask = (submask - 1) & availableMask)
if (validDistribution[i][submask])
dp[i][mask] = dp[i][mask] || dp[i + 1][mask | submask];
}
return dp[0][0];
}
private:
vector<int> getFreqs(const vector<int>& nums) {
vector<int> freqs;
unordered_map<int, int> count;
for (const int num : nums)
++count[num];
for (const auto& [_, freq] : count)
freqs.push_back(freq);
return freqs;
}
vector<vector<bool>> getValidDistribuition(const vector<int>& freqs,
const vector<int>& quantity) {
const int maxMask = 1 << quantity.size();
vector<vector<bool>> validDistribution(freqs.size(), vector<bool>(maxMask));
for (int i = 0; i < freqs.size(); ++i)
for (int mask = 0; mask < maxMask; ++mask)
if (freqs[i] >= getQuantitySum(quantity, mask))
validDistribution[i][mask] = true;
return validDistribution;
}
// Returns the sum of the selected quantity represented by `mask`.
int getQuantitySum(const vector<int>& quantity, int mask) {
int sum = 0;
for (int i = 0; i < quantity.size(); ++i)
if (mask >> i & 1)
sum += quantity[i];
return sum;
}
};
/* code provided by PROGIEZ */1655. Distribute Repeating Integers LeetCode Solution in Java
class Solution {
public boolean canDistribute(int[] nums, int[] quantity) {
List<Integer> freqs = getFreqs(nums);
// validDistribution[i][j] := true if it's possible to distribute the i-th
// freq into a subset of quantity represented by the bitmask j
boolean[][] validDistribution = getValidDistribution(freqs, quantity);
final int n = freqs.size();
final int m = quantity.length;
final int maxMask = 1 << m;
// dp[i][j] := true if it's possible to distribute freqs[i..n), where j is
// the bitmask of the selected quantity
boolean[][] dp = new boolean[n + 1][maxMask];
dp[n][maxMask - 1] = true;
for (int i = n - 1; i >= 0; --i)
for (int mask = 0; mask < maxMask; ++mask) {
dp[i][mask] = dp[i + 1][mask];
final int availableMask = ~mask & (maxMask - 1);
for (int submask = availableMask; submask > 0; submask = (submask - 1) & availableMask)
if (validDistribution[i][submask])
dp[i][mask] = dp[i][mask] || dp[i + 1][mask | submask];
}
return dp[0][0];
}
private List<Integer> getFreqs(int[] nums) {
List<Integer> freqs = new ArrayList<>();
Map<Integer, Integer> count = new HashMap<>();
for (final int num : nums)
count.merge(num, 1, Integer::sum);
return new ArrayList<>(count.values());
}
boolean[][] getValidDistribution(List<Integer> freqs, int[] quantity) {
final int maxMask = 1 << quantity.length;
boolean[][] validDistribution = new boolean[freqs.size()][maxMask];
for (int i = 0; i < freqs.size(); ++i)
for (int mask = 0; mask < maxMask; ++mask)
if (freqs.get(i) >= getQuantitySum(quantity, mask))
validDistribution[i][mask] = true;
return validDistribution;
}
// Returns the sum of the selected quantity represented by `mask`.
int getQuantitySum(int[] quantity, int mask) {
int sum = 0;
for (int i = 0; i < quantity.length; ++i)
if ((mask >> i & 1) == 1)
sum += quantity[i];
return sum;
}
}
// code provided by PROGIEZ1655. Distribute Repeating Integers LeetCode Solution in Python
class Solution:
def canDistribute(self, nums: list[int], quantity: list[int]) -> bool:
freqs = list(collections.Counter(nums).values())
# validDistribution[i][j] := True if it's possible to distribute the i-th
# freq into a subset of quantity represented by the bitmask j
validDistribution = self._getValidDistribution(freqs, quantity)
n = len(freqs)
m = len(quantity)
maxMask = 1 << m
# dp[i][j] := true if it's possible to distribute freqs[i..n), where j is
# the bitmask of the selected quantity
dp = [[False] * maxMask for _ in range(n + 1)]
dp[n][maxMask - 1] = True
for i in range(n - 1, -1, -1):
for mask in range(maxMask):
dp[i][mask] = dp[i + 1][mask]
availableMask = ~mask & (maxMask - 1)
submask = availableMask
while submask > 0:
if validDistribution[i][submask]:
dp[i][mask] = dp[i][mask] or dp[i + 1][mask | submask]
submask = (submask - 1) & availableMask
return dp[0][0]
def _getValidDistribution(self, freqs: list[int],
quantity: list[int]) -> list[list[bool]]:
maxMask = 1 << len(quantity)
validDistribution = [[False] * maxMask for _ in range(len(freqs))]
for i, freq in enumerate(freqs):
for mask in range(maxMask):
if freq >= self._getQuantitySum(quantity, mask):
validDistribution[i][mask] = True
return validDistribution
def _getQuantitySum(self, quantity: list[int], mask: int) -> int:
"""Returns the sum of the selected quantity represented by `mask`."""
return sum(q for i, q in enumerate(quantity) if mask >> i & 1)
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.