1

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.

Improve this question
4
  • 2
    The question is not appropriate. You cannot expect us to give the solution to your homework. Try something and show us if you do not understand anything. Commented Jan 29, 2015 at 10:19
  • Oh, well, I'm not really even sure where to start to be honest. It's not a homework, it's just a problem I hit and I can't wrap my head around where to start Commented Jan 29, 2015 at 10:21
  • Intuitively, if the size of the array should be, say 5, and the sum should be, say, 50, you could do with, [10,10,10,10,10]. Except that those are not distinct. So how to make them distinct, and make the difference between smallest and larges minimal? Well, isn't that just [8,9,10,11,12]? Commented Jan 29, 2015 at 10:26
  • Can you provide more details about the problem? how large are N and S? Commented Jan 29, 2015 at 10:28

2 Answers 2

Reset to default
3

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     
}
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

We need to minimize the difference between the largest and the smallest element, so it looks like diff should be distributed as +1 among the last diff elements of the array, not added to the last one.
@ILoveCoding modified my answer, so I added the different in last dif number :)
What does the "f" function do?
@Alexandr updated, it returns the sum of N consecutive numbers, started from a
@PhamTrung: this looks like a good answer, but without any prior effort from the OP, I am not entirely certain anything has been learned.
3

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, ...}
Improve this answer

3 Comments

You made your job easy by picking S that is divisible by N. What if S is 31 now?
@dasblinkenlight Looping around seems to work fine. It will be {2, 3, 4, 5, 6, 7, 9} for S = 31.
@dasblinkenlight I rephrase the last sentence. The aim is not to compute an exact result but to find a good start for the algorithm. For example, if S = 10_000, it is useless to start with {1,2,3,4,5,6}. It will be better to start with {1660,1661,1662,1663,1664,1665}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.