programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

M Hasan
Ranch Hand
Posts: 35
Problem: Write a program which takes an array of positive int and returns the smallest number which is not the sum of the subset of that array.

I solved it but took me long. I did it myself but I did not understand when I debug it. Here is the code:

debug loop 1: 1 > 0 + 1: no maxConstructableValue  + a = 1 but why not 1 + 1 = 2 cause in the if statement I already incremented maxConstructableValue + 1.

Carey Brown
Saloon Keeper
Posts: 3315
46
M Hasan wrote:Problem: Write a program which takes an array of positive int and returns the smallest number which is not the sum of the subset of that array.

I solved it but took me long. I did it myself but I did not understand when I debug it.

The problem needs some additional clarification. If you have
int[] array = {12, 2, 1, 15, 2, 4};
and 'n' is a one of the elements in the original set, then 'n' would be rejected because 'n' is the sum of the elements in the set {n}. Therefore none of the elements in the original set would pass this test. Would the "subset" have to contain two or more values? Would the subset have to NOT contain the element being tested, in which case a test of '2' would fail because of the set {2}(the other '2')?

I'm afraid that your code does not come up with permutations of subsets that can be summed and compared to an individual element from the original set to see if it passes the test or not.

Junilu Lacar
Sheriff
Posts: 11485
180
M Hasan wrote:cause in the if statement I already incremented maxConstructableValue + 1

No, you didn't. That expression simply uses the current value of maxConstructableValue and adds it to 1, it doesn't change the value that the variable holds.

M Hasan
Ranch Hand
Posts: 35
thanks Junilu Lacar But if it is not incremented at the if statement then why the first debug 1 > 0 false and it is going to maxConstructableValue += a;

Junilu Lacar
Sheriff
Posts: 11485
180
M Hasan wrote:thanks Junilu Lacar But if it is not incremented at the if statement then why the first debug 1 > 0 false and it is going to maxConstructableValue += a;

Again, you have it wrong. This is what you have in the first iteration:

a = 1
maxConstructableValue = 0,

→ if (a > maxConstructableValue + 1)
→ if (1 > 0 + 1)
→ if (1 > 1)
→ if (false)

Campbell Ritchie
Marshal
Posts: 56536
172
What do they mean by subset? Arrays don't have subsets; they may have included ranges or sequences however. Does it say anything about the size of the included range/subrange you are looking for?

Carey Brown
Saloon Keeper
Posts: 3315
46
• 1
An array or List can hold a "set" that permits duplicate entries where an actual "Set" object does not. A "subset" would be a new set (List in our case) that contains some, but not all, of the elements of a given set.

Carey Brown
Saloon Keeper
Posts: 3315
46
• 1

 Consider Paul's rocket mass heater.