Given an array of size N, I need to find the minimum number of values ​​that will be summed within the minimum and maximum range

Question

Given an array of size N, I need to find the minimum number of values ​​that will be summed within the range of min and max.

For example: consider an array [1,2,3,4,5]. I need to find the minimum number of values ​​from this array, the sum of which is more than 5 and less than 8. Ans: since 1 + 5 is more than 5 and less than 8, so the minimum number of values ​​is 2, therefore, the answer.

And below, my function implements the logic.

int void CheckValue() { for (i = 0; i <5; i++) if (a[i] > min && a[i] < max) return 1; for (i = 0; i< 4; i++) for (j = i + 1; j < 5; j++) if (a[i] + a[j] > min && a[i] + a[j] < max) return 2; for (i = 0; i < 3; i++) for (j = i + 1; j < 4; j++) for (k = j+1; k < 5; k++) if (a[i] + a[j] + a[k] > min && a[i] + a[j] + a[k] < max) return 3; for (i = 0; i < 2; i++) for (j = i + 1; j< 3; j++) for (k = j + 1; k< 4; k++) for (l = k + 1; l < 5; l++) if (a[i] + a[j] + a[k] + a[l] > min && a[i] + a[j] + a[k] + a[l] < max) return 4; if(a[0]+a[1]+a[2]+a[3]+a[4]>min && a[0]+a[1]+a[2]+a[3]+a[4]<max) return 5; return 0; } 

It works great, but the problem is its complexity. Can anyone give any suggestions for optimizing this code further or provide better logic for implementing this.

Answer 1

I would suggest the following solution:

Assume that the minimum value for the range is minVal and the maximum value is maxVal. Now sort the array. Suppose the length of the array is len. Do a binary search for a number in the array that is <= maxVal.

Search: I mean, if the number is in index i, then the number with index i + 1 should be> = maxVal. Suppose the index of this number is currIndex. If this number is maxVal, then do a binary search between 0 and currIndex for the number

minVal and

Search Error: This is the average highest number - the array is smaller than maxVal. Therefore, for this case, do the following: 1) Add the largest number to the array in the result set. 2) Now run the loop from len-1 t0 1. If arr [len-1] + arr [len] is less than maxVal, then add arr [len-1] to the result set and continue the loop. If arr [len-1] + arr [len]> maxVal, then skip and check for arr [len-1] + arr [len].

etc.

Answer 2

I have no experience in such things, so there is a possibility that there are better ways to do this, but I have some ideas that might be useful.

You are currently calculating all possible combinations, you should be able to modify your algorithm to make it so that you can eliminate some combinations without calculating them.

I would sort the array to start, which will allow you to eliminate some values ​​without calculating them.

For example, if you have an array that looks like [1,2,4,5,9] and min = 11 and max = 14, then your algorithm checks 1 + 2,1 + 4,1 + 5,1 + 9 , then 2 + 4, 2 + 5, 2 + 9, 4 + 5, 4 + 9, before coming to an answer.

If instead you start with the highest number, first you can eliminate all possible 1 combinations by calculating 9 + 1, since 9 + 1 <= 11, it should be so that all other possible 1 combinations are not valid for the two sum total The same with all 2 possible combinations. If you add this logic to your code, you should have less unnecessary calculations, hoping to speed up your code.

Answer 3

Is this a homework question?

Your question is really not clear, but here is what I would like to:

Sorting. NlogN .
Start by adding the first item and the last item. Is it in range? Take the first pointer from one end, say from the beginning, move it to the middle and add the average and last number, the first pointer + the last pointer. what's in the range? you can move the first pointer to the middle between the first and last pointer, that is: on the right 3/4 of the sequence.

So you are using binary search here with two pointers to a sorted sequence.

This will give you an estimate of the number of elements that will be in range. I hope you have this idea.

You can move the second pointer to the middle if your amount is out of range.

This will give you nlogn .

Please note that these are just two numbers, I'm not sure if you are asking for all possible numbers whose complement will be in the range or only two numbers?

two numbers are easy, nlogn does it

All possible subsets is the problem of the sum of the subsets, which is np hard . exponential, which is 2 ** n .

Answer 4

I think you should consider sorting your array, there are many efficient algorithms for this.

Then start with the largest value and cummulatively add the smaller values ​​in sorted order, checking the condition at each step.

Answer 5

This is a rather complex problem, which is likely to be tough.

One thing that comes to mind is that it is a bit like a “satchel problem”. Perhaps you can find an implementation for this and adapt it.

---

If the minimum number of elements should be small, you can, of course, use the brute force method:

• Set minVal = 1
• Find all minVal size sets
• While none of the sets match your criteria, add 1 to minVal and go to step 2