Swift solution - DP


  • 0
    class Solution {
        /// An easy recurrence for this problem is f[i] = f[i / 2] + i % 2.
        func countBits(_ num: Int) -> [Int] {
            if num < 0 {
                return []
            }
            
            var dp = [Int](repeatElement(0, count: num + 1))
            
            for i in 0...num {
                dp[i] = dp[i >> 1] + (i & 1)
            }
            
            return dp
        }
        
        func countBits2(_ num: Int) -> [Int] {
            if num < 0 {
                return []
            }
            if num == 0 {
                return [0]
            }
            
            var dp = [Int](repeatElement(0, count: num + 1))
            
            for i in 1...num {
                dp[i] = dp[i & (i - 1)] + 1
            }
            
            return dp
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.