Skip to content

Instantly share code, notes, and snippets.

@fschr

fschr/countOnes.py

Created September 28, 2015 21:25
Show Gist options
  • Save fschr/98f011d32f176058e32e to your computer and use it in GitHub Desktop.
Save fschr/98f011d32f176058e32e to your computer and use it in GitHub Desktop.
Download ZIP
Raw
countOnes.py
class Wrapper:
memo = dict()
@staticmethod
def countOnes(n):
if n == 0:
return 0
if n == 1:
Wrapper.memo[1] = 1
return 1
val = 1 + Wrapper.countOnes(n - 2**(n.bit_length() - 1))
Wrapper.memo[n] = val
return val
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment