Round 1
Questions: You call a number beautiful if it contains at least 1 bit '0' and at most 3 bits '0' in its binary representation. For example, 5 (101) and 8 (1000) are beautiful numbers but numbers like 15 (1111), and 16 (10000) are not. You are given Q queries of the type L, R. Consider all beautiful numbers between the range L and R (inclusive). Find the sum of cubes of all such beautiful numbers. Since the sum can be very large, output it modulo 998244353.
- Q Represents an integer denoting the number of queries
- queries: Represents a 2D array/vector denoting queries of the type 'L R' Therefore, the size of queries array is Q*2.
The first line contains a single integer Q denoting the number of queries. The next Q lines follow. For each line: The first line contains two space-separated integers denoting L and R.
Output format: Print Q space-separated integers, where the integer represents the sum of cubes of beautiful numbers in range L and R (inclusive). Do not forget to take modulo 998244353.
Constraints:
1 <= Q <= 2*1e5
1 <= L <= R <= 1e18
Candidate's Approach
-
Identify Beautiful Numbers:
- A number is beautiful if its binary representation has between 1 and 3 zeros.
- Generate all numbers up to a certain limit and check their binary representation.
-
Precompute Beautiful Numbers:
- Precompute all beautiful numbers up to 1e18 and store them in a list.
-
Query Processing:
- For each query, filter the precomputed beautiful numbers to find those within the range [L, R].
- Calculate the sum of cubes of these numbers and take modulo 998244353.
-
Efficiency:
- Use binary search to quickly find the range of beautiful numbers for each query.
Interviewer's Feedback
No feedback provided.