Browser tab content: Problem List
0
Debugging...
Run
Submit
00:00:00
Description
Editorial
Editorial
Solutions
Solutions
Submissions
Submissions
Code
Note
Note
Testcase
Testcase
Test Result
338. Counting Bits
Easy
Topics
Companies
Hint

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

 

Example 1:

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10


Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101


 

Constraints:

0 <= n <= 105

 

Follow up:

It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?
Seen this question in a real interview before?
1/5
Yes
No
Accepted
1.2M
Submissions
1.5M
Acceptance Rate
79.0%
Topics
Dynamic Programming
Bit Manipulation
Companies
0 - 6 months
Amazon
4
6 months ago
Adobe
7
Bloomberg
6
Google
5
Uber
5
Meta
3
Yahoo
3
Microsoft
2
Apple
2
Nvidia
2
Hint 1
You should make use of what you have produced already.
Hint 2
Divide the numbers in ranges like [2-3], [4-7], [8-15] and so on. And try to generate new range from previous.
Hint 3
Or does the odd/even status of the number help you in calculating the number of 1s?
Similar Questions
Number of 1 Bits
Easy
Sum of Values at Indices With K Set Bits
Easy
Find the K-or of an Array
Easy
Discussion (87)
Choose a type
Preview
Comment
💡 Discussion Rules

1. Please don't post any solutions in this discussion.

2. The problem discussion is for asking questions about the problem or for sharing tips - anything except for solutions.

3. If you'd like to share your solution for feedback and ideas, please head to the solutions tab and post it there.

Sort by:Best
No comments yet.
1
2
3
4
5
6
9
Copyright ©️ 2024 LeetCode All rights reserved
11.2K
87
Java
Auto
1
2
3
4
5
class Solution {
    public int[] countBits(int n) {
        
    }
}
Saved
Ln 1, Col 1
You must run your code first

Integer to English Words - LeetCode

Problem List
Tag
264. Ugly Number II

Med.

265. Paint House II

Hard

266. Palindrome Permutation

Easy

267. Palindrome Permutation II

Med.

268. Missing Number

Easy

269. Alien Dictionary

Hard

270. Closest Binary Search Tree Value

Easy

271. Encode and Decode Strings

Med.

272. Closest Binary Search Tree Value II

Hard

273. Integer to English Words

Hard

274. H-Index

Med.

275. H-Index II

Med.

276. Paint Fence

Med.

277. Find the Celebrity

Med.

278. First Bad Version

Easy

279. Perfect Squares

Med.

280. Wiggle Sort

Med.

281. Zigzag Iterator

Med.

282. Expression Add Operators

Hard

283. Move Zeroes

Easy

284. Peeking Iterator

Med.

285. Inorder Successor in BST

Med.

286. Walls and Gates

Med.

287. Find the Duplicate Number

Med.

288. Unique Word Abbreviation

Med.

289. Game of Life

Med.

290. Word Pattern

Easy

291. Word Pattern II

Med.

292. Nim Game

Easy

293. Flip Game

Easy

294. Flip Game II

Med.

295. Find Median from Data Stream

Hard

296. Best Meeting Point

Hard

297. Serialize and Deserialize Binary Tree

Hard

298. Binary Tree Longest Consecutive Sequence

Med.

299. Bulls and Cows

Med.

300. Longest Increasing Subsequence

Med.

301. Remove Invalid Parentheses

Hard

302. Smallest Rectangle Enclosing Black Pixels

Hard

303. Range Sum Query - Immutable

Easy

304. Range Sum Query 2D - Immutable

Med.

305. Number of Islands II

Hard

306. Additive Number

Med.

307. Range Sum Query - Mutable

Med.

308. Range Sum Query 2D - Mutable

Hard

309. Best Time to Buy and Sell Stock with Cooldown

Med.

310. Minimum Height Trees

Med.

311. Sparse Matrix Multiplication

Med.

312. Burst Balloons

Hard

313. Super Ugly Number

Med.

314. Binary Tree Vertical Order Traversal

Med.

315. Count of Smaller Numbers After Self

Hard

316. Remove Duplicate Letters

Med.

317. Shortest Distance from All Buildings

Hard

318. Maximum Product of Word Lengths

Med.

319. Bulb Switcher

Med.

320. Generalized Abbreviation

Med.

321. Create Maximum Number

Hard

322. Coin Change

Med.

323. Number of Connected Components in an Undirected Graph

Med.

324. Wiggle Sort II

Med.

325. Maximum Size Subarray Sum Equals k

Med.

326. Power of Three

Easy

327. Count of Range Sum

Hard

328. Odd Even Linked List

Med.

329. Longest Increasing Path in a Matrix

Hard

330. Patching Array

Hard

331. Verify Preorder Serialization of a Binary Tree

Med.

332. Reconstruct Itinerary

Hard

333. Largest BST Subtree

Med.

334. Increasing Triplet Subsequence

Med.

335. Self Crossing

Hard

336. Palindrome Pairs

Hard

337. House Robber III

Med.

338. Counting Bits

Easy

339. Nested List Weight Sum

Med.

340. Longest Substring with At Most K Distinct Characters

Med.

341. Flatten Nested List Iterator

Med.

342. Power of Four

Easy

343. Integer Break

Med.

344. Reverse String

Easy

345. Reverse Vowels of a String

Easy

346. Moving Average from Data Stream

Easy

347. Top K Frequent Elements

Med.

348. Design Tic-Tac-Toe

Med.

349. Intersection of Two Arrays

Easy

350. Intersection of Two Arrays II

Easy

351. Android Unlock Patterns

Med.

352. Data Stream as Disjoint Intervals

Hard

353. Design Snake Game

Med.

354. Russian Doll Envelopes

Hard

355. Design Twitter

Med.

356. Line Reflection

Med.

357. Count Numbers with Unique Digits

Med.

358. Rearrange String k Distance Apart

Hard

359. Logger Rate Limiter

Easy

360. Sort Transformed Array

Med.

361. Bomb Enemy

Med.

362. Design Hit Counter

Med.

363. Max Sum of Rectangle No Larger Than K

Hard

364. Nested List Weight Sum II

Med.

365. Water and Jug Problem

Med.

366. Find Leaves of Binary Tree

Med.

367. Valid Perfect Square

Easy

368. Largest Divisible Subset

Med.

369. Plus One Linked List

Med.

370. Range Addition

Med.

371. Sum of Two Integers

Med.

372. Super Pow

Med.

373. Find K Pairs with Smallest Sums

Med.

374. Guess Number Higher or Lower

Easy

375. Guess Number Higher or Lower II

Med.

376. Wiggle Subsequence

Med.

377. Combination Sum IV

Med.

378. Kth Smallest Element in a Sorted Matrix

Med.

379. Design Phone Directory

Med.

380. Insert Delete GetRandom O(1)

Med.

381. Insert Delete GetRandom O(1) - Duplicates allowed

Hard

382. Linked List Random Node

Med.

383. Ransom Note

Easy

384. Shuffle an Array

Med.

385. Mini Parser

Med.

386. Lexicographical Numbers

Med.

387. First Unique Character in a String

Easy

388. Longest Absolute File Path

Med.

389. Find the Difference

Easy

390. Elimination Game

Med.

391. Perfect Rectangle

Hard

392. Is Subsequence

Easy

393. UTF-8 Validation

Med.

394. Decode String

Med.

395. Longest Substring with At Least K Repeating Characters

Med.

396. Rotate Function

Med.

397. Integer Replacement

Med.

398. Random Pick Index

Med.

399. Evaluate Division

Med.

400. Nth Digit

Med.

401. Binary Watch

Easy

402. Remove K Digits

Med.

403. Frog Jump

Hard

404. Sum of Left Leaves

Easy

405. Convert a Number to Hexadecimal

Easy

406. Queue Reconstruction by Height

Med.

407. Trapping Rain Water II

Hard

408. Valid Word Abbreviation

Easy

409. Longest Palindrome

Easy

410. Split Array Largest Sum

Hard

411. Minimum Unique Word Abbreviation

Hard

412. Fizz Buzz

Easy

413. Arithmetic Slices

Med.

Remove distracting text, extract the programming question, provide simple, common, and optimized Java solution for it.