leetcode 338) Counting Bits

LV. Easy 😎

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

Counting Bits - LeetCode

 

문제

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 <= 10^5

 

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++)?

 

문제 해결법

2의 거듭제곱들을 찾아가며 풀어주면 쉽게 해결 가능하다.

2의 거듭제곱이 넘어갈 때마다 digit를 바꿔주고

해당 수를 digit으로 나눠서 나온 나머지 값을 앞에서 찾아 +1을 해서 ans에 넣어주면 된다.

 

해결 코드

class Solution {
public:
	vector<int> countBits(int n) {
		int digit = 1;
		int temp = 0;
		vector<int> ans;

		ans.push_back(0);
		for (int i = 1; i <= n; ++i) {
			temp = ans[i % digit] + 1;
			ans.push_back(temp);
			if (digit * 2 == i)
				digit = i;
		}
		return ans;
	}
};