<reponame>Roxxum/Coding-Challenges<filename>SOLVED/counting-bits.py
"""
Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.
Â 
Example 1:
Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

Example 2:
Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

Â 
Constraints:

0 <= n <= 105

Â 
Follow up:

It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?


"""

# define an input for testing purposes
from typing import Counter

n = 255

# actual code to submit
def solution(n: int) -> list:
    answer = []

    for number in range(n+1):
        binary = Counter(bin(number)[2:])
        answer.append(binary["1"])

    return answer

# use print statement to check if it works
print(solution(n))

# My submission: https://leetcode.com/submissions/detail/597775768/
"""
Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.
Â 
Example 1:
Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

Example 2:
Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

Â 
Constraints:

0 <= n <= 105

Â 
Follow up:

It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?


"""

# define an input for testing purposes
from typing import Counter

n = 255

# actual code to submit
def solution(n: int) -> list:
    answer = []

    for number in range(n+1):
        binary = Counter(bin(number)[2:])
        answer.append(binary["1"])

    return answer

# use print statement to check if it works
print(solution(n))

# My submission: https://leetcode.com/submissions/detail/597775768/
Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i. Â  Example 1: Input: n = 2 Output: [0,1,1] Explanation: 0 --> 0 1 --> 1 2 --> 10  Example 2: Input: n = 5 Output: [0,1,1,2,1,2] Explanation: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101  Â  Constraints:  0 <= n <= 105  Â  Follow up:  It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass? Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)? # define an input for testing purposes # actual code to submit # use print statement to check if it works # My submission: https://leetcode.com/submissions/detail/597775768/