This Code Review, so let us review your code, before proceeding to questions and optimisations.
Code and style review
- Choose better names – According to python style guide, PEP8, you should use
snake_case
for variables and functions. In addition what does dp
, acc
stand for? And in general one should avoid single letter variables except in tight loops
- Uncomfortable while loop – I'm a little confused by the loop in
humbleNumber
, you have loop using i
and n
, but mostly you focus and increment on curr
. This doesn't read good, and is somewhat confusing.
- Anti-pattern of
if True: variable = True
– Setting a variable to True
or False
after you just checked it in an if statement, is kind of an anti-pattern. Normally you should rather do dp[curr] = ishumble[curr, dp)
. In your code this does require some other changes as well. See code refactor below
- Add spaces after commas – Don't clamp up list like in
[2,3,5,7]
, add spaces around operations and after commas. It is better with [2, 3, 5, 7]
and ishumble(x, dp)
and so on
- Comment your code – Add docstrings to your functions, and comment before non-intuitive code segments
- BUG:
ishumble(x/i)
is missing the dp
parameter – When testing a slightly modification of your code, I actually got to call the line which you comment that you don't get called, and it fails as it hasn't gotten enough parameters! (So yes, it doesn't get called in your version, and no, it doesn't work!)
Code refactored
After correcting these issue you could end up with:
def humble_number(n):
"""Return n'th number divisble only by 2, 3, 5 and 7."""
humble_numbers = {}
i, humble_candidate = 0, 0
while i < n:
# Find next humble number
while True:
humble_candidate += 1
humble_numbers[humble_candidate] = ishumble(humble_candidate, humble_numbers)
if humble_numbers[humble_candidate]:
break
i += 1
return humble_candidate
You could do similar refactoring to the ishumble
, but you should really replace that function with something more effective.
Time and space complexity
Your code is not plain \$O(n)\$. At least not \$n\$ as the n'th humble number. This comes from the simple fact that you loop all numbers, curr
, until you find your n'th humble numbers, and the 1689th humble number is 330674. Clearly you've checked 330674 numbers to get the 1689th humble numbers, and that is not \$O(n)\$. In addition your method uses a dict to store previously calculated humble numbers, so it has a memory complexity of \$\theta (n)\$.
A better approach would be to use generators to calculate the next humble number, using the information that the next number has to be next multiple of 2, 3, 5, or 7 compared to a previous humble number. Various approaches exists to do this, amongst them the one in Barrys answer (which got written while I write this answer), or the one suggests from Martin R from Rosetta code related to Hamming numbers.
If you exchange Rosetta Code's hamming()
(Cyclic generator #2) with the following you'll get a quite fast version:
def humble_number(a, b = None):
if not b:
b = a + 1
seq = (chain([1], pp(7, pp(5, pp(3, p(2))))))
return list(islice(seq, a - 1, b - 1))