[NEW] Add solution for Counting Bits #107
Description
🎯 Problem Information
- Problem Name: Counting Bits
- CSES Link: https://cses.fi/problemset/task/1146
- Category: Bitwise Operations
- Estimated Difficulty: [Medium]
📋 Problem Description
Your task is to count the number of one bits in the binary representations of integers between 1 and n.
💡 Proposed Approach
- Each bit position (0th, 1st, 2nd, ...) follows a repeating pattern:
0 for 2^i numbers, then 1 for 2^i numbers. - For each bit i:
- Count how many complete 0–1 cycles fit into 1..n.
- Add remaining 1s from the incomplete cycle.
- Time Complexity: O(log n)
- Space Complexity: O(1)
📝 Implementation Notes
Any special considerations or optimizations needed:
- Requires fast I/O
- Needs modular arithmetic
- Large input constraints
- Edge cases to consider
🏷️ Labels
Please add appropriate labels:
-
hacktoberfest(if contributing during Hacktoberfest) -
good first issue(if suitable for beginners) -
help wanted(if you need assistance)
👤 Assignee
- I would like to work on this issue
- I'm available for guidance/review
📎 Additional Context
Add any other context or screenshots about the problem here.