#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
through9
inclusive) that when added will equalz
.
More details:
- For example, if
z
is3
, your program will find that four permutations of digits add up to that value (3
,2+1
,1+1+1
, and1+2
), and thus return4
. - 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 equalling3
. - Use of a single digit is acceptable as a permutation: e.g.
3
is itself a valid permutation of digits that add up to3
. makeNumberBasic(z)
is looking for permutations, not combinations:1+5
and5+1
would count as two unique possible ways to add to6
, not one. Read more about permutations vs. combinations here.- If no permutations of the digits
1
through9
add up to the numberz
, your function should return0
.
#####Find out more about basic challenges.
###Intermediate difficulty
Write
makeNumber(z)
so that it only returns the number of combinations of unique digits from1
to9
.
- For example, if
z
is3
, your program will find the unique combinations3
and1+2
, and thus return2
. - To clarify unique digits: repeat use of a digit is no longer acceptable.
1+5
,1+2+3
,2+4
, and3+3
all equal6
, butmakeNumber(z)
would not consider3+3
a valid combination as it uses the digit3
more than once. makeNumber(z)
is now looking for combinations not permutations:1+5
and5+1
would now only be accepted as one possible way to add digits1
through9
to6
, not two.
#####Find out more about intermediate challenges.
###Hard Difficulty
Write versions of
makeNumberBasic(z)
and ofmakeNumber(z)
(the normal and intermediate difficulty challenges) as efficiently as possible.
#####Find out more about hard challenges and Big O
###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:
- the rules & how to participate in challenges
- how challenges are used as job interview questions
- why Codecademy runs challenges (and why they are formatted this way)
- more details about the challenges and why we think they are useful.
- find previous challenges (and see the past winners) in our Challenge Index