I need to find out the amount of times that the number one is in a number. Here is what I have:
Sample input: 11001
Desired output: 3
def oneCount(n):
n = str(n)
if n == '1':
return 1
else:
return 1 + oneCount(n[:-1])
print oneCount(1100)
Right now it returns the amount of digits but not the amount of ones.
def oneCount(n):
n = str(n)
# Here, you check if the entire string is '1'.
# Not sure if you mean to check if a single digit is '1'.
if n == '1':
return 1
else:
# If the entire string is not '1', you recur on all but the least significant digit.
return 1 + oneCount(n[:-1])
print oneCount(1100)
Walk:
oneCount(1100) -> '1100' is not '1'. recurs on 1 + oneCount('110')
1 + oneCount('100') -> '110' is not '1'. recurs on 1 + (1 + oneCount('11'))
2 + oneCount('00') -> '11' is not '1'. recurs on 2 + (1 + oneCount('1'))
3 + oneCount('0') -> '1' is '1'. return 1
4
OK, so that's a wrong answer, but perhaps more insidious, what if your most significant digit weren't 1?
oneCount(2)
>>> RuntimeError: maximum recursion depth exceeded while calling a Python object
You end up recurring on the empty string. The empty string isn't '1', so the recursion is infinite!
When recurring over an iterable like a string or a list, a good rule of thumb is to consider the empty iterable your base case.
def oneCount(i):
i = str(i)
if i == '':
return 0
# Do not recur in the base case, above
# The below cases are not the base case, so expect to recur
# What is the nature of the recursion?
car, cdr = i[0], i[1:] # silly lisp reference
if car == '1':
???
# else?
Consider that a boolean value is equivalent to an integer value of 1 or 0 in Python. You can add that value to an integer.
return (car == 1) + oneCount(cdr)
Consider that you don't need to convert an integer into a string in order to iterate over it. Consider cdr, car = divmod(i, 10), or more plainly, cdr, car = i // 10, i % 10. What's fun is that gives you the ability to count the occurrence of digits in a number in any base.
def oneCount(i, base=10):
if i == 0:
return 0
cdr, car = divmod(i, base)
if car == 1:
???
???
>>> oneCount(int('111111100000', 2), 2)
7
A simple solution:
def oneCount(n):
n = str(n)
# if we have reached the end of n return 0
if not n:
return 0
# check current n[0] is == 1 and move right one char in n
else:
return (n[0] == "1") + oneCount(n[1:])
I didn't want to answer this in the first place, but all the bad answers kind of force me to...
First of all, a recursion as a terminal case and a recursive case. The terminal case is the case where you can immediately tell the result. For your task, it is the empty string, because it contains zero ones:
if n == '':
return 0
In the recursive case, you have to check wheter your string starts with a 1 or not:
if n.startswith('1'):
return 1+oneCount(n[1:])
else:
return oneCount(n[1:])
Also, you are converting n to a string every time, which is not neccessary.
A pythonic solution would use if not n: instead of if n == '':, so a complete solution could look like
def oneCountRecur(n):
if not n:
return 0
if n.startswith('1'):
return 1 + oneCountRecur(n[1:])
else:
return oneCountRecur(n[1:])
def oneCount(n):
return oneCountRecur(str(n))
The else: above return oneCountRecur(n[1:]) can be left out, it's a matter of personal taste.
else isn't optional, without it you don't always return.
None if n does not start with 1. And give a exception since you can't add None to a integer
else is optional.if statement and just do return n.startswith('1') + oneCountRecur(n[1:])Since you insists on a recursive solution. Here we go
def oneCount(n):
digits = str(n)
count = 1 if digits.startswith('1') else 0
for digit in digits[1:]: # start looping from next digit
count += oneCount(digit)
return count
EDIT: In case you dont consider the above function as recursive enough:
def oneCount(n):
digits = str(n)
count = 1 if digits.startswith('1') else 0
if len(digits) > 1:
count += oneCount(digits[1:])
return count
for, I'd clearly use for digit in digits: ....def oneCount(n):
if not n:
return 0
else:
return (n % 10 == 1) + oneCount(n // 10)
Fiver?return (n[-1] == '1') + oneCount(n[:-1])