Simple recursive function to find missing number in a permutation

Question

This is a short and simple Python written to help me sharpen my dulling recursion skills. It expects a sorted permutation of integers n1..n2 in list format, with a single step missing (e.g., [10,11,13]). I know it does nothing to check errors; I'm more interested in theory here.

from __future__ import division
from math import ceil
def f(lis):
 A = lis[:int(ceil(len(lis))/2)]
 B = lis[int(ceil(len(lis))/2):]
 ISA = sum(range(A[0], A[0] + len(A))) # "Ideal" Sum of A
 ISB = sum(range(B[0], B[0] + len(B))) # "Ideal" Sum of B
 if sum(A) > ISA:
 return f(A)
 elif sum(B) > ISB:
 return f(B)
 else:
 return B[0] - 1

Any thoughts on whether or not this is a decent solution? Any suggested improvements (especially in regard to time complexity)? Is there a more performant algorithm I could compare this to as a heuristic?

• Ryan Dougherty: Does the missing step include the 2 ends of the list, or is it strictly in the middle?
• Chase Ries: I'm not totally sure I understand, but strictly in the middle, I think. If the step itself was at either end, the list wouldn't appear to have a step missing at all. I think I can safely exclude that as a special condition that would be checked for elsewhere because it would require additional information to determine which end of the list it would be found at.
• Ryan Dougherty: That's what I was thinking. You actually don't need recursion for this problem, and you only need linear time and constant space.

Answer 1

As others pointed out in comments (and as usual), an iterative solution can be better. But you said you want to practice recursion, so I guess you want to stick with that.

This code:

int(ceil(len(lis))/2)

Is exactly the same as:

len(lis) // 2

Because, there's no point taking the ceiling of a list length, as it's always an integer. And you can use // to divide and throw away the remainder, which is the same thing as casting a floating point number to integer, but shorter and simpler.

You should not duplicate code. You should put the result of the above calculation only once, save it in a variable and reuse it when creating A and B.

Similarly, instead of duplicating the logic when creating ISA and ISB, it would be better to put the common logic into a function.

Some more meaningful variable and function names would be good too.

• Chase Ries: Oops! Haha, that first point was a throwback to how I started attacking the problem at first and I didn't remove it.
• Chase Ries: I understand not duplicating code, but I felt like making a function for such a simple but specific calculation was pretty aggressive. It would add another name to the namespace that I would never use again. Do you recommend that kind of granularity for functions all the same?
• janos: Yes. But you don't have to pollute the namespace: you can define the function inside this function
• Chase Ries: Wouldn't that redefine the function at every level of recursion though? Isn't that bad form somehow?
• janos: It wouldn't redefine, and it's not bad form, it's actually encouraged

Answer 2

Since we can assume without loss of generality that the missing number is not on the ends of the list, let's assume that the numbers are: a, a+1, ..., a+k-1, a+k+1, ..., a+n. Therefore, only a+k is missing from the list (but of course, we don't know what that is yet!).

For a range of integers a, a+1, ..., b without any missing, the sum of them is (a-b-1)(a+b)/2. So all we need to do is to sum all of the integers in the given list, and subtract that sum from the (a-b-1)(a+b)/2, as:

def findMissing(l):
 n = len(l)
 if n == 0:
 return 0
 if n == 1:
 return l[0]
 # len(l) is >= 2
 a = min(l)
 b = max(l)
 fullSum = (b+1-a)*(a+b)//2
 sumInList = sum(l)
 return fullSum - sumInList
print(findMissing([10, 11, 13])) # prints 12
print(findMissing([1, 2, 3, 4, 5, 7, 8, 9, 10, 11])) # prints 6
print(findMissing([13, 11, 12, 9, 8])) # prints 10 (even though out of order)

We actually don't need to sort the list because all we need are the max and min of the array, which takes linear time instead of n log(n) time.

In fact, this does something even stronger: find the sum of all missing items from the list. Of course, if there is only 1 item missing, the number returned is the missing item.

• Chase Ries: Is there a name for this approach? Also, where does the n come from in n log(n) time -- the call to sum()?
• Ryan Dougherty: Sorry, I forgot to mention: n is the length of the list l. Sorting a list of size n in general takes n log(n) time.