follow up of leetcode 338, counting bits
https://leetcode.com/problems/counting-bits/description/?envType=daily-question&envId=2023-09-01unknown
c_cpp
a year ago
502 B
7
Indexable
Never
// AMAN JAIN MCA 1st YEAR 2nd SEM // time O(N), space O(N) // Approach: Basic right shifting combined with DP class Solution { public: vector<int> countBits(int n) { vector<int> dp; dp.push_back(0); if(n == 0) return dp; dp.push_back(1); if(n == 1) return dp; int i = 1; while(++i <= n) { if(i % 2 == 0) dp.push_back(dp[i/2]); else dp.push_back(1 + dp[i/2]); } return dp; } };