CODEWITHSUNDEEP
arraysalgorithmdynamicdynamic-programming
Alexandr
Alexandr

Reputation: 726

Dynamic programming - fixed sum of fixed size array

Here is a problem I am stuck on:

Two integers are given: N (the size of the array) and S (the required sum of all elements of the array)

The requirements are to construct an array of size N and with the sum of its elements S in such a way that:

  • The array is to contain N positive non-zero values

  • The elements of the vector are distinct

  • The absolute difference between the largest and smallest element in the array is minimal

  • If there are more than 1 solutions in which this absolute difference is equal, the minim-lexicographic solution will be shown.

I can't really wrap my head around how to start the problem. Any help would be lovely.

Upvotes: 1

Views: 584

Answers (2)

Pham Trung
Pham Trung

Reputation: 11294

Sum of first N positive value {1,2,3...N) is (N + 1)*N/2

So, we can easily come up with a formula for sum of N consecutive positive numbers (starting at a)

((N + a - 1) + a)*N/2 = (N + 2*a - 1)*N/2

Using binary search, we can find the N consecutive numbers with largest starting number a have sum <= S.

So let dif = S - (N + 2*a - 1)*N/2 -> so the the last dif numbers should be add with 1 and the rest N - dif numbers are N - dif + a, ..., a .

Pseudo code

int start = 1;
int end = S;
int result = 1;
while(start <= end){
    int mid = (start + end)/2;
    int sum = sum(mid);   
    if(sum <= S){
       result = max(mid,result); 
       start = mid + 1;
    }else{
       end = mid - 1;
    } 
}
//So we know that the sequence starting at result
//Now we need to find the diff
int dif = S - sum(result);

for(int i = 0; i < N; i++){
   if(i >= N - dif ){//last N - dif number is added one
      print (i + result + 1);

   }else{
      print (i + result);
   }
}

int sum(int a){//Return sum from a to N + a - 1
    return (N +2*a - 1)*N/2     
}

Upvotes: 3

Arnaud Denoyelle
Arnaud Denoyelle

Reputation: 31283

I think that it is possible to do it by construction.

Take N = 6 and S = 30

1) Initialize your array like this : {1,2,3,4,5,6}

2) Loop and increment from the latest to the first :

{1,2,3,4,5,6} S = 21
{1,2,3,4,5,7} S = 22
{1,2,3,4,6,7} S = 23
{1,2,3,5,6,7} S = 24
{1,2,4,5,6,7} S = 25
{1,3,4,5,6,7} S = 26
{2,3,4,5,6,7} S = 27

Loop again : 

{2,3,4,5,6,7} S = 27
{2,3,4,5,6,8} S = 28
{2,3,4,5,7,8} S = 29
{2,3,4,6,7,8} S = 30

Maybe there is a formula to find a good start. For example, you can start with : 

 {S/N - N, S/N - N+1, S/N - N+2, ...}

Upvotes: 3

Related Questions