Panda Guru LogoPanda
Guru

Moveworks | OA | SDE1 | 2024-2025

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.

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
  1. 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.
  2. Precompute Beautiful Numbers:

    • Precompute all beautiful numbers up to 1e18 and store them in a list.
  3. 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.
  4. Efficiency:

    • Use binary search to quickly find the range of beautiful numbers for each query.
Interviewer's Feedback

No feedback provided.