• Post Reply Bookmark Topic Watch Topic
  • New Topic
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.

 
Ranch Hand
Posts: 33
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Please correct me If I am wrong?

 
Saloon Keeper
Posts: 6049
58
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Divyadharshini Karthikeyan
Ranch Hand
Posts: 33
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@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: 137
7
IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.

 
Rancher
Posts: 3305
28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Divyadharshini Karthikeyan
Ranch Hand
Posts: 33
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@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: 3415
149
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Divyadharshini,

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: 3305
28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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: 3415
149
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I excluded that possibility, since I wuld like to see art least one of the base numbers in the results.
 
Mike Simmons
Rancher
Posts: 3305
28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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: 3305
28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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: 3415
149
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 3415
149
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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...
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!