In: Computer Science
Java problem
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
HINT
import java.util.Scanner;
class Solution
{
static boolean isKPartitionPossibleRec(int arr[], int subsetSum[], boolean taken[],
int subset, int K, int N, int curIdx, int limitIdx)
{
if (subsetSum[curIdx] == subset)
{
/* current index (K - 2) represents (K - 1) subsets of equal
sum last partition will already remain with sum 'subset'*/
if (curIdx == K - 2)
return true;
// recursive call for next subsetition
return isKPartitionPossibleRec(arr, subsetSum, taken, subset,
K, N, curIdx + 1, N - 1);
}
// start from limitIdx and include elements into current partition
for (int i = limitIdx; i >= 0; i--)
{
// if already taken, continue
if (taken[i])
continue;
int tmp = subsetSum[curIdx] + arr[i];
// if temp is less than subset then only include the element
// and call recursively
if (tmp <= subset)
{
// mark the element and include into current partition sum
taken[i] = true;
subsetSum[curIdx] += arr[i];
boolean nxt = isKPartitionPossibleRec(arr, subsetSum, taken,
subset, K, N, curIdx, i - 1);
// after recursive call unmark the element and remove from
// subsetition sum
taken[i] = false;
subsetSum[curIdx] -= arr[i];
if (nxt)
return true;
}
}
return false;
}
// Method returns true if arr can be partitioned into K subsets
// with equal sum
static boolean canDistribute(int arr[], int K)
{
int N=arr.length;
// If K is 1, then complete array will be our answer
if (K == 1)
return true;
// If total number of partitions are more than N, then
// division is not possible
if (N < K)
return false;
// if array sum is not divisible by K then we can't divide
// array into K partitions
int sum = 0;
for (int i = 0; i < N; i++)
sum += arr[i];
if (sum % K != 0)
return false;
// the sum of each subset should be subset (= sum / K)
int subset = sum / K;
int []subsetSum = new int[K];
boolean []taken = new boolean[N];
// Initialize sum of each subset from 0
for (int i = 0; i < K; i++)
subsetSum[i] = 0;
// mark all elements as not taken
for (int i = 0; i < N; i++)
taken[i] = false;
// initialize first subsubset sum as last element of
// array and mark that as taken
subsetSum[0] = arr[N - 1];
taken[N - 1] = true;
// call recursive method to check K-substitution condition
return isKPartitionPossibleRec(arr, subsetSum, taken,
subset, K, N, 0, N - 1);
}
}
class HomeworkAssignment5_2
{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
System.out.println("Please neter size of array");
int size=sc.nextInt();
int res[]=new int[size];
for(int i=0;i<size;i++)
{
res[i]=sc.nextInt();
}
System.out.println("Please enter value of k");
int k=sc.nextInt();
Solution obj=new Solution();
if(obj.canDistribute(res,k))
System.out.println("true");
else
System.out.println("false");
}
}
Here is the desired code. I hope it helps.