[Challenge] Number Permutation

#Code Challenge #7: May 24, 2017

Every week, we feature the type of brain-teasing question that might be asked in a full-stack developer’s job interview at places such as Google and Facebook.

This week’s challenge was reportedly asked in interviews at Facebook:


###Basic Difficulty

Create a program makeNumberBasic(z) which, when given an input of a number (z), returns the number of all possible permutations of digits (1 through 9 inclusive) that when added will equal z.

More details:

  • For example, if z is 3, your program will find that four permutations of digits add up to that value (3, 2+1, 1+1+1, and 1+2), and thus return 4.
  • You may limit makeNumberBasic(z) to the use of five digits
  • Repeat use of a digit is acceptable: e.g. 1+1+1 would be a valid addition of digits equalling 3.
  • Use of a single digit is acceptable as a permutation: e.g. 3 is itself a valid permutation of digits that add up to 3.
  • makeNumberBasic(z) is looking for permutations, not combinations: 1+5 and 5+1 would count as two unique possible ways to add to 6, not one. Read more about permutations vs. combinations here.
  • If no permutations of the digits 1 through 9 add up to the number z, your function should return 0.

#####Find out more about basic challenges.


###Intermediate difficulty

Write makeNumber(z) so that it only returns the number of combinations of unique digits from 1 to 9.

  • For example, if z is 3, your program will find the unique combinations 3 and 1+2, and thus return 2.
  • To clarify unique digits: repeat use of a digit is no longer acceptable. 1+5, 1+2+3, 2+4, and 3+3 all equal 6, but makeNumber(z) would not consider 3+3 a valid combination as it uses the digit 3 more than once.
  • makeNumber(z) is now looking for combinations not permutations: 1+5 and 5+1 would now only be accepted as one possible way to add digits 1 through 9 to 6, not two.

#####Find out more about intermediate challenges.

###Hard Difficulty

Write versions of makeNumberBasic(z) and of makeNumber(z) (the normal and intermediate difficulty challenges) as efficiently as possible.

#####Find out more about hard challenges and Big O

Our sample solution

###Winner:

@lmreia had a great use of recursion and needed the fewest “runs” through the main problem of the body to solve, making it faster than other recursion solutions. See their solution here and our comments here.


####Scroll down and reply to this thread with your code to participate! Don’t just submit your code, remember to explain your solution, too! it is now too late to be considered under our “best code” assessment, but please include a link to your code running on repl.it and abide by our other simple rules.


The fine print:

Click the links to find out more about:

Intermediate Difficulty: Code

Explanation: I made 5 nested “for” loops to iterate trought all the possible cases, I also take in count that the case “i = z” it’s added to the answer adding one to the solution at the returning phase.

To make sure that the code returns the combinations of unique digits I also make sure that all of the digits are unique with a function called “uniqueDigit” for any run of the loop, also I just take in count the cases where “i < j” and “j < k” and “k < l” and " l < m" so this kind of cases (1,2) = (2,1) will not happend.

3 Likes

Hi,

Please find below my solution to the Basic and Intermediate versions of this challenge.
I created a function that divide a integer number z by 2 and find the two integers i1 and i2 such that i1 + i2 = z.
By doing it successively, I am able to find all the numbers whose sum results in z.

Basic version:
https://repl.it/ITtR/2

Intermediate version:
https://repl.it/IQaO/2

Thanks to alexcraig for useful observations.

Edit:
Now the solutions have a max of x digits (x is read in the console).

2 Likes

I’ve understood the logic of your code…but I’m afraid your code doesn’t seem to be running!:confused:
Please check your code once again.

1 Like

Basic level. Five for loops for every term and an if-statement.

3 Likes

Could you please give me more details about this issue?
Did you try typing a given number in the console?

1 Like

Basic and intermediate levels.

The program takes two arguments:
z - the input number
max_length - the maximum number of unique elements which sum should give z value

I decided to combine both basic and intermediate solutions in one function to make it easier to read.

3 Likes

I’m sorry it was an input error, now it’s working propertly :grinning:

1 Like

There are no issues regarding your code. I tried typing a number on the console, and got the correct output. Good job. Happy Coding! :smiley:

1 Like

Awesome code! Keep it up!:grinning:

2 Likes

Solution to the intermediate level…but I need help in limiting the number of digits to 5…all suggestions are welcome.

2 Likes

I hope my comments are good enough to explain the code.
The only major difference between the two is the range of the for loop inside the recursion function.

Changing the function to return only the number of permutations/combinations instead of a list of all possible permutations/combinations would be very simple.

Code

C++ version of the same code: link

3 Likes

Hey all, for your answer to be considered the winner we need to see two solutions, 1 for the basic version and 1 for the intermediate version, both refined to be as efficient as possible. Preferably put both solutions in one repl.it file called makeNumberBasic and makeNumber .

Also, a combination of just one digit is valid. I.e. the ways to make 2 are : 1+1 & 2 Or for the intermediate difficulty just 2.

And some notes so far:
Firstly, every one of these solutions is a very nice implementation! I’m just posting ways it could be made even better…


@gargol12 your code needs to:[quote=“danieloduffy, post:1, topic:85775”]
limit NumberMaker(z) to the use of five digits
[/quote]

you only use three.


@smreia there is quite a lot of redundant code in your solution, For example when you check n1 != n2 this is already checked in the if block above it, perhaps have another look through to make it more efficient.


@fredswed your code includes 0:


@rd0122 if you’re looking for efficiency, there’s a few places you can neaten up the code. E.g.

nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
av_nums = [x for x in nums if x < z]

can be turned into:
av_nums = [x for x in range (1,10) if x < z]

And you do a couple of slow calculations multiple times instead of using some temp variables. On the other hand you also use temp variables where they’re not needed. If you look over your code there’s one place that you could add an extra line rather than having 6 lines at the bottom of your code.

Your code will be a really really great solution if you make some of these changes :slight_smile:


@shrinkhla same as a few above your code allows for 0. Also please use repl.it , if you wish your code to be considered when looking for the winner :slight_smile:


@lmreia it seems like your recursion checks too many different inputs. If you can cut this down this would be a very good contender for best solution. E.g. for 3 your program runs the inside of that for loop 78 times. Whereas you only really need to check:

1 - small
1 + 1 - small
1 + 2 - correct break
2 - small
3 - correct break

So in an optimum world it would only run the middle of the for loop 5 times. Also, could you edit your code so it assumes a max of 5 possible digits, as stated in the challenge description, or so it has a max of x digits.


Hope this helps everyone, don’t forget the two key points at the start!!


8 Likes

Thanks a lot for the help and guidance, really appreciate it :relaxed:
I’ve made changes in my code an linked them to repl.it .

2 Likes

Okej. So I am working on maximize the value of terms to nine and also getting rid of zeros so 2+4+0+0+0 will be just 2+4.

2 Likes

Thanks for the advice. I have made some changes in my code.

2 Likes

Thank you for the advice, I’ll edit my code so it fits your considerations.

Update: The new version of the code it’s up! :smiley:

3 Likes

Thanks for great feedback! I will try to work on this :slight_smile:

Update:
I’ve edited my code!

2 Likes

Thanks for the useful observations.
I tried to optmize the code as you said and also created a basic version the challenge.

2 Likes

Prints the total number + list of all possible permutations - combinations in the same function both basic & intermediate solution.

2 Likes