CODEWITHSUNDEEP
arraysalgorithmmathcomplexity-theory
Srdjan Ristanovic
Srdjan Ristanovic

Reputation: 23

Find way to separate array so each subarrays sum is less or equal to a number

I have a mathematical/algorithmic problem here.

Given an array of numbers, find a way to separate it to 5 subarrays, so that sum of each subarrays is less than or equal to a given number. All numbers from the initial array, must go to one of the subarrays, and be part of one sum.

So the input to the algorithm would be: d - representing the number that each subarrays sum has to be less or equal A - representing the array of numbers that will be separated to different subarrays, and will be part of one sum

Algorithm complexity must be polynomial. Thank you.

Upvotes: 0

Views: 140

Answers (2)

Junwei su
Junwei su

Reputation: 138

Set up of the problem: d : the upper bound for the subarray A : the initial array

Assuming A is not sorted. (Heuristic) Algorithm:

1.Sort A in ascending order using standard sorting algorithm->O(nlogn)

2.Check if the largest element of A is greater than d ->(constant) if yes, no solution if no, continue 3.Sum up all the element in A, denote S. Check if S/5 > d ->O(n) if yes, no solution if no, continue

4.Using greedy approach, create a new subarray Asi, add next biggest element aj in the sorted A to Asi so that the sum of Asi does not exceed d. Remove aj from sorted A ->O(n)

  1. repeat step4 until either of the condition satisfied:

    I.At creating subarray Asi, there are only 5-i element left In this case, split the remaining element to individual subarray, done

    II. i = 5. There are 5 subarray created.

The algorithm described above is bounded by O(nlogn) therefore in polynomial time.

Upvotes: 0

John Coleman
John Coleman

Reputation: 51998

If by "subarray" you mean "subset" as opposed to "contiguous slice", it is impossible to find a polynomial time algorithm for this problem (unless P = NP). The Partition Problem is to partition a list of numbers into to sets such that the sum of both sets are equal. It is known to be NP-complete. The partition problem can be reduced to your problem as follows:

Suppose that x1, ..., x_n are positive numbers that you want to partition into 2 sets such that their sums are equal. Let d be this common sum (which would be the sum of the xi divided by 2). extend x_i to an array, A, of size n+3 by adding three copies of d. Clearly the only way to partition A into 5 subarrays so that the sum of each is less than or equal to d is if the sum of each actually equals d. This would in turn require 3 of the subarrays to have length 1, each consisting of the number d. The remaining 2 subarrays would be exactly a partition of the original n numbers.

On the other hand, if there are additional constraints on what the numbers are and/or the subarrays need to be, there might be a polynomial solution. But, if so, you should clearly spell out what there constraints are.

Upvotes: 1

Related Questions