FilesExpand file tree

 master

/

counting-bits.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

59 lines (50 loc) · 1.77 KB

 master

/

counting-bits.py

Copy path

Top

File metadata and controls

• Code
• Blame

59 lines (50 loc) · 1.77 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

# https://leetcode.com/problems/counting-bits/

# Example:

# For num = 5 you should return [0,1,1,2,1,2].

#

# Follow up:

#

# It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?

# Space complexity should be O(n).

# Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

# First Solution

# Yeah , Just noticed that I should be doing it like a Boss , without using inbuild count functions LOL !

class Solution(object):

def countBits(self, num):

"""

:type num: int

:rtype: List[int]

"""

my_list = []

self.num = num

for i in xrange(self.num+1):

my_list.append(bin(i)[2:].count('1'))

return my_list

# Second Solution

# Hope this is more BOSS , since I have my own count function now - I still think there might be some bit manipulation trick here

class Solution(object):

def countBits(self, num):

"""

:type num: int

:rtype: List[int]

"""

my_list = []

self.num = num

for i in xrange(self.num+1):

my_list.append(self.my_count(bin(i),1))

return my_list

def my_count(self,number,search_char):

self.count = 0

self.number = str(number)

self.search_char = str(search_char)

for i in xrange(len(self.number)):

#print "search_character = ",self.search_char

#print self.number[i]

if self.number[i] == self.search_char:

self.count = self.count + 1

else:

continue

return self.count

my_solution = Solution()

print my_solution.countBits(5)

#print my_solution.my_count('11111',1)