This week's book giveaway is in the Java in General forum.We're giving away four copies of Event Streams in Action and have Alexander Dean & Valentin Crettaz on-line!See this thread for details.
Win a copy of Event Streams in Action this week in the Java in General forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Devaka Cooray
• Liutauras Vilda
• Jeanne Boyarsky
• Bear Bibeault
Sheriffs:
• Paul Clapham
• Knute Snortum
• Rob Spoor
Saloon Keepers:
• Tim Moores
• Ron McLeod
• Piet Souris
• Stephan van Hulst
• Carey Brown
Bartenders:
• Tim Holloway
• Frits Walraven
• Ganesh Patekar

# Given N, count the number of ways to express N as sum of 1, 3 and 4. ORDER MATTERS.

Greenhorn
Posts: 28
Please correct me If I am wrong?

Saloon Keeper
Posts: 6042
58
I would need a better explanation of the requirements. What does it mean "order matters"? When you only return a count there is no concept of order. Order would seem to imply an array of some sort.

Greenhorn
Posts: 28
@Carey Brown

For 4
The ways are
1. 1+1+1+1
2. 3+1 (here 1+3 and 3+1 are not same and counted as separate ways)
3. 1+3
4. 4

so total number of ways for 4(as a sum of 1,3,4) is 4 and the output is not 3.

Hope you got my explanation?

Rancher
Posts: 124
7
I'm not sure I'm getting the exercise. For the number 4, why isn't 2+2 a valid way?

Edit: I see it was specified in the subject line.

Carey Brown
Saloon Keeper
Posts: 6042
58
What if N is 5 or 6?

Rancher
Posts: 3302
27
5 or 6 seem to work.  What about -1?

Once you handle -1 and other negative numbers, you may be able to remove some of the other special cases.

Greenhorn
Posts: 28
@Carey Brown
if  N=5
1. 1 +1 + 1+ 1+ 1
2. 1+1+3
3. 1+3+1
4. 3+1+1
5. 4+1
6 1+4

so totally 6 ways ,
similarly for N=6

Saloon Keeper
Posts: 3413
149

Your code looks correct, but it has a flaw and it is very inflexible.

When N == 0, your code returns 1, That is incorrect: there is no way you can write 0 as a combination of 1, 3, or 4.
So, I would start my method with:

Now, with this your sub1, sub2 and sub3 are no longer correct. How would you change these?

And my final remark: your current code is very inflexible. What if you want to do the same exercise, but then for the numbers 2, 5, 6, 10? Therefore, suppose that your baseNumbers are in a List<Integer>, and your method would become:

How would you implement that?

Mike Simmons
Rancher
Posts: 3302
27

Piet Souris wrote:When N == 0, your code returns 1, That is incorrect: there is no way you can write 0 as a combination of 1, 3, or 4.

I disagree, there is exactly one way: with zero ones, zero threes, and zero fours.  The empty set is a subset of all sets.

There is no way the total can be negative.  But there is exactly one way to get zero: by choosing zero of each number.

Philosophical arguments aside, once you code for n<0 and n==0, you don't need any of the other special cases (testing for n==1, n==2, n==3) - you just get the right answers.  Provided you return 1 for n==0.

Piet Souris
Saloon Keeper
Posts: 3413
149
I excluded that possibility, since I wuld like to see art least one of the base numbers in the results.

Mike Simmons
Rancher
Posts: 3302
27

Piet Souris wrote:I excluded that possibility, since I wuld like to see art least one of the base numbers in the results.

I didn't get what you're saying here, sorry.  Can you say it another way please?  I assume the very minor typos resolve to

Piet Souris wrote:I excluded that possibility, since I would like to see at least one of the base numbers in the results.

but I'm still not sure what that means here.

Mike Simmons
Rancher
Posts: 3302
27

Piet Souris wrote:Therefore, suppose that your baseNumbers are in a List<Integer>

I would argue this is more properly a Set<Integer>. But I like the idea of generalizing it all - there's a very compact solution out there, waiting to be found.

Piet Souris
Saloon Keeper
Posts: 3413
149
• 1
Okay, a Set instead of a List, and I just revised my code to incorporate the return of 1 when N == 0! Made it shorter.

Piet Souris
Saloon Keeper
Posts: 3413
149
• 1

Mike Simmons wrote:

Piet Souris wrote:I excluded that possibility, since I wuld like to see art least one of the base numbers in the results.

I didn't get what you're saying here, sorry.  Can you say it another way please?  I assume the very minor typos resolve to

excuses for the typos! I missed this reply at first.

I just meant that if the baseNumberSet = { 1, 3, 4}, then I do not want "" to be a valid solution for N == 0. But I find my argument pretty weak, with hindsight...