LeetCode 75
Counting Bits
- Problem
- LC 338
- Topic
- Bit Manipulation
- File
- official75_LC338CountingBits.java
- Path
- pkg5leetcode/official75/official75_LC338CountingBits.java
- Package
- pkg5leetcode.official75
- Command
- java pkg5leetcode/official75/official75_LC338CountingBits.java
- Approach
- dp[i] = dp[i>>1] + (i&1).
- Complexity
- Time O(n), Space O(n)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.official75;2 3/*4 * Counting Bits | LC 3385 * APPROACH: dp[i] = dp[i>>1] + (i&1).6 * COMPLEXITY: Time O(n), Space O(n)7 */8public class official75_LC338CountingBits {9 static int[] countBits(int n) {10 int[] dp = new int[n + 1];11 for (int i = 1; i <= n; i++) dp[i] = dp[i >> 1] + (i & 1);12 return dp;13 }14 15 public static void main(String[] args) {16 check(java.util.Arrays.equals(countBits(2), new int[]{0,1,1}), "case1");17 check(java.util.Arrays.equals(countBits(5), new int[]{0,1,1,2,1,2}), "case2");18 System.out.println("all tests passed");19 }20 21 static void check(boolean cond, String name) {22 if (!cond) throw new AssertionError("FAILED: " + name);23 System.out.println(" PASS " + name);24 }25}