Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

197. Counting Bits

EasyDay 58 of 60Bit Manipulation & Math

Given an integer n, return an array ans of length n + 1 where ans[i] is the number of 1 bits in the binary form of i, for every i from 0 to n. Try to do it in O(n) time without counting each number bit by bit.

Example 1
Input: n = 2
Output: [0,1,1]
0 is 0, 1 is 1, 2 is 10.
Example 2
Input: n = 5
Output: [0,1,1,2,1,2]
Constraints
  • 0 <= n <= 10^5
Hints
Frequently asked at: Amazon, Apple, Adobe
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min