# Distribute Repeating Integers

This page explains Java solution to problem `Distribute Repeating Integers` using `Backtracking` algorithm.

## Problem Statement

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 = 
Output: false
Explanation: The 0th customer cannot be given two different integers.

Example 2:

Input: nums = [1,2,3,3], quantity = 
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].

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.*;

class DistributeRepeatingIntegers {
public boolean canDistribute(int[] nums, int[] quantity) {
HashMap<Integer, Integer> freqMap = new HashMap<>();
for(int i = 0; i < nums.length; i++) {
freqMap.put(nums[i], freqMap.getOrDefault(nums[i], 0) + 1);
}

int[] count = new int[freqMap.size()];
int index = 0;
for(int value: freqMap.values()) count[index++] = value;

Arrays.sort(quantity);
return helper(quantity, count, quantity.length - 1);
}

private boolean helper(int[] quantity, int[] count, int qIndex) {
if(qIndex == -1) return true;

for(int i = 0; i < count.length; i++) {
int required = quantity[qIndex];

if(count[i] >= required) {
count[i] -= required;

if(helper(quantity, count, qIndex - 1)) return true;

count[i] += required;
}
}
return false;
}
}
``````

## Time Complexity

O(MN) Where
M is number of customer orders
N is number of values in an array.

## Space Complexity

O(M) Where
M is number of customer orders