문제
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.
Example 1:
Input: 2 Output: [0,1,1] Example 2:
Input: 5 Output: [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.
풀이
예를들어 숫자 5가 주어지면 0, 1, 2, 3, 4, 5를 2진수로 변환했을때 각 숫자가 몇개의 1을 갖는지 배열로 만들어서 리턴하는 문제이다. 0은 0개, 1은 1개 2는 이진수로 10이니까 1개 3은 이진수로 11이니까 2개이다.풀이가 생각이 안나서 1부터 15까지의 숫자를 2진수로 변환해보고 패턴을 살펴봤다. D[i]를 숫자 i를 이진수로 변환했을때 1의 개수라고 놓으면, D[i]는 i를 2로 나눈 숫자를 이진수로 변환했을떄 1의 개수를 그대로 가져오고 맨 끝자리가 1이냐 0이냐에 따라서 1이 한개 더 추가된다.
결과
