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.

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

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.

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].

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.

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

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(M^N) 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