Question

This program should be written in Java language.

Given the uncertainty surrounding the outbreak of the Coronavirus disease (COVID-19) pandemic, our federal government has to work tirelessly to ensure the distribution of needed resources such as medical essentials, water, food supply among the states, townships, and counties in the time of crisis.

You are a software engineer from the Right Resource, a company that delivers logistic solutions to local and state entities (schools, institutions, government offices, etc). You are working on a software solution to check that given a set of resources, whether they can be proportioned and distributed equally to k medical facilities. Resources are represented as an array of positive integers. You want to see if these resources can be sub-divided into k facilities, each having the same total sum (of resources) as the other facilities. For example with resources = {1,2,3,4,5,6} we can sub-divide them into k = 3 medical facilities, each having the same total sum of 7: {1,6}, {2,5}, and {3,4}.

STARTER CODE

Write a solution method, canDistribute, that returns whether it is possible (true or false) that a given set of resources divides into k equal-sum facilities. You will solve this problem using a recursion:

public class HomeworkAssignment5_2 {    
   public static void main(String[] args) {
      // just like any problems, whatever you need here, etc.
   }
}
class Solution {
   // YOUR STYLING DOCUMENTATION GOES HERE
   public boolean canDistribute(int[] resources, int groups) { 
      // YOUR CODE HERE 
   }
}

EXAMPLES

input: {3,4,5,6}, 2

output: true

Explanation: {3,6}, {4,5}

input: {1}, 1

output: true

Explanation: {1}

input: {1, 3, 2, 3, 4, 1, 3, 5, 2, 1}, 5

output: true

Explanation: {3,2}, {4,1}, {5}, {2,3}, {1,3,1}

input: {1}, 4

output: false

Explanation: cannot split further with a value of 1 in resource.

CONSTRAINTS / ASSUMPTIONS

• 0 < resources.length() < 1000.
• 0 < medical facilities < 1000.
• A sub-divided facility is never empty.
• The solution method returns false if resources cannot be evenly distributed, true otherwise.
• There may be more than one ways to sub-divide a given set of resources into k facilities. Doesn't matter. Your solution should return true in that case.
• You will use a Recursion for this. Failure to do so received -4 points.

HINT

• Note: you may choose to solve this problem in your own way or use the following pseudo code.
• Check for all boundary conditions to return result immediately if known, e.g., resources.length() = 1 and k = 1, return true, resources.length() = 1 and k = 4, return false, etc.
• Find the purported allocation for each group, i.e., allocation = SUM(resources)/k.
• Sort the resources in either ascending or descending order.
• Create another solution method of your choice to enable recursion.
• Remaining Pseudo Code:
  1. Create an empty array of integers with k elements. This is your "memory buffer". At the end of your recursion, you want this memory buffer be filled with equally allocated values, allocation.
  2. Pick the highest resource (one with the highest integral value) in your resources.
  3. Check if the selected resource is <= allocation:
     • If yes, add that value to the first available element in your memory buffer of k elements. Go to #4.
     • If not, move on to other elements in your memory buffer to see if there's available space to accommodate it.
     • If there's no available space to accommodate the selected resource, it is impossible for resources to be allocated equally.
  4. Advance to the next highest resource. Repeat Step #3. If all resources have been considered and there is no more next highest, go to Step #5.
  5. Check if every element in your memory buffer has the same value. If so you have an evenly allocated distribution - return true. False otherwise.

Answer 1

import java.util.Arrays;

public class HomeworkAssignment5_2 {
public static void main(String[] args) {
// just like any problems, whatever you need here, etc.
   Solution solution = new Solution();
   System.out.println(solution.canDistribute(new int[]{3,4,5,6}, 2));
   System.out.println(solution.canDistribute(new int[]{1}, 1));
   System.out.println(solution.canDistribute(new int[]{1, 3, 2, 3, 4, 1, 3, 5, 2, 1}, 5));
   System.out.println(solution.canDistribute(new int[]{1}, 4));
}
}
//There may be more than one ways to sub-divide a given set of resources into k facilities. Doesn't matter. Your solution should return true in that case.
class Solution {
// YOUR STYLING DOCUMENTATION GOES HERE
//   The solution method returns false if resources cannot be evenly distributed, true otherwise.
public boolean canDistribute(int[] resources, int groups) {
//   resources.length() = 1 and k = 1, return true, resources.length() = 1 and k = 4, return false, etc.
   int sum = Arrays.stream(resources).sum();   
if (sum % groups > 0) return false;
// Find the purported allocation for each group, i.e., allocation = SUM(resources)/k.
int allocation = sum / groups;
// Sort the resources in either ascending or descending order.
Arrays.sort(resources);
int subDivided = resources.length - 1;
if (resources[subDivided] > allocation) return false;
while (subDivided >= 0 && resources[subDivided] == allocation) {
subDivided--;
groups--;
}
// Create another solution method of your choice to enable recursion.
return find(new int[groups], subDivided, resources, allocation);
}
public boolean find(int[] groups,int subDivided,int[] resources,int allocation) {
//   A sub-divided facility is never empty.
       if (subDivided < 0) return true;
//       Create an empty array of integers with k elements
       int v = resources[subDivided];
       for (int i = 0; i < groups.length; i++) {
//           Check if the selected resource is <= allocation:
//           If yes, add that value to the first available element in your memory buffer of k elements. Go to #4.
       if (groups[i] + v <= allocation) {
       groups[i] += v;
       if (find(groups, subDivided - 1, resources, allocation)) return true;
       groups[i] -= v;
       }
       if (groups[i] == 0) break;
       }
       return false;
}
}