Geek Answers Handbook

Limited amount of a subset to a specified range

i has an array that contains only 2 types of numbers (x and x-1), for example: - {5,5,4,4,5,5,5}, and I am assigned a range of 12-14 (inclusive). I already know that the length of the array is constant 7, and I also know how many elements of each type are in the array (count)

now I need to find if there is any combination of elements in the array whose sum falls into this range.

All I need is the number of elements in the subset, the sum of which falls into this range.

I solved this problem using brute force as follows, but it is very effective.

here count is the number x-1 in the array

for(int i=0;i<=7-count;i++){ for(int j=0;j<=count;j++){ if(x*(i)+(x-1)*j>=min && x*(i)+(x-1)*j<=max){ output1=i+j; } } }

can anyone tell me if there is a better way to solve this

example: -

the given array is {5,5,4,4,5,5,5}, and the given range is 12-14.

therefore, I would choose a subset {5,5,4} whose sum is 14, and therefore the answer to the number of elements in the subset will be 3. {5,4,4} can also be selected in this solution

+4
source share
2 answers

You can improve your brute force using some analysis.

where N is the length of the array, and n is the result:

 0 <= n <=N 0 <= j <= count 0 <= i <= N - count n = i + j -> j <= n sum = x * i + (x - 1) * j = x * n - j min <= x * n - j <= max -> x * n - max <= j <= x * n - min min <= x * n - j -> n >= (min + j) / x >= min / x x * n - j <= max -> n <= (max + j) / x <= (max + count) / x

To summarize, you can use your own loop, but with a different range:

 for (int n = min / x; n <= min (N, (max + count) / x); n++) { for (int j = max (0, x * n - max); j <= min (count, x * n - min, n); j++) { sum = x * n - j; if (sum >= min && sum <= max) { output1 = n; } } }

PS: there is some kind of picture here that can help understand the idea of ​​the graph http://i.zlowiki.ru/110917_768e5221.jpg

+2
source

say you want to know the number of a and b that add to n . When testing the number a you only need to use division to find the number b .

i.e.

number of a * a + number of b * b = n

So

number of b = ( n - number of a * a ) / b ;

EDIT: if this number is an integer, you have a solution.

To check if the division is an integer, you can do

 (`n` - `number of a` * `a`) % `b` == 0

if you have a range spread that is less than b , you can do

 (`min` - `number of a` * `a`) % `b` <= `max` - `min`

if the spread is greater than or equal to b , you always have a number of solutions.

I assume b positive.

0
source

More articles:


All Articles