[LeetCode] 338. Counting Bits (C#)

Young_A 2024. 1. 13. 06:35

LeetCode - Problems - Algorithms - 338. Counting Bits

Counting Bits - LeetCode

Can you solve this real interview question? Counting Bits - 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

leetcode.com

Solutions from leetcode community (C#)

public class Solution {
    public int[] CountBits(int n) {
        //time complexity O(n log n)
        // 0 1 2 3 => 0 1 1 2
        // next set of four numbers last two digits has same num of 1 like above line
        // e.g. [4, 5, 6, 7] => [1, 2, 2, 3]
        // 4: 0100 = 1 + dp[n - 4]
        // 5: 0101 = 1 + dp[n - 4]
        // 6: 0110 = 1 + dp[n - 4]
        // 7: 0111 = 1 + dp[n - 4]

        // 8: 1000 = 1 + dp[n - 8]
        // and so on

        // 1: 0001 = 1 + dp[n - 1]
        // 2: 0010 = 1 + dp[n - 2]
        // 3: 0011 = 1 + dp[n - 2]
        // 4: 0100 = 1 + dp[n - 4]
        // 5: 0101 = 1 + dp[n - 4]
        // 6: 0110 = 2
        // 7: 0111 = 3
        // 8: 1000 = 1 + dp[n - 8]

        if (n == 0) return new int[] {0};
        if (n == 1) return new int[] {0, 1};

        var bits = new int[n + 1];
        bits[0] = 0;
        bits[1] = 1;


        for(int i = 2; i <= n; i++)
        {
            if (i % 2 == 0)
            {
                bits[i] = bits[i / 2];
            }
            else
            {
                bits[i] = bits[i / 2] + 1;
            }
        }

        return bits;
    }
}

Comments

이해될듯 하면서도 이해가 안됨!!

결국 계속 틀리다가 솔루션 찾아봄.

원리는 알겠는데 코드로 구현이 어떻게 된건지가 애매모호하다.

아무래도 코딩을 2년 넘게 쉰 영향이 있는 듯