Blind 75
Counting Bits
- Problem
- LC 338
- Category
- Binary
- File
- blind75_LC338CountingBits.java
- Path
- pkg5leetcode/blind75/blind75_LC338CountingBits.java
- Package
- pkg5leetcode.blind75
- Command
- java pkg5leetcode/blind75/blind75_LC338CountingBits.java
- Approach
- DP bits[i] = bits[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.blind75;2 3/*4 * Counting Bits | LC 3385 * APPROACH: DP bits[i] = bits[i>>1] + (i&1).6 * COMPLEXITY: Time O(n), Space O(n)7 */8public class blind75_LC338CountingBits {9 static int[] countBits(int n) {10 int[] bits = new int[n + 1];11 for (int i = 1; i <= n; i++) bits[i] = bits[i >> 1] + (i & 1);12 return bits;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}