Asked in: ADOBE
Image of the Question
All Testcases Passed ✔
Solution
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// ... rest of solution available after purchaseExplanation
```
To solve the problem of finding the Kth "lucky number" within the range [L, R], where a lucky number is defined as any number whose binary representation contains the substring "101", you need a strategic approach since the constraints on L, R, and K are extremely large (up to 10^18). Direct brute force checking each number between L and R is computationally impossible due to time constraints and range size.
Start by understanding the core challenge:
1. How to efficiently identify if a number is lucky (contains "101" in binary)
2. How to quickly count how many lucky numbers exist up to a given number N
3. How to find the Kth lucky number in a given range [L, R]
Step 1: Represent the Problem Using Patterns in Binary
The key insight is to analyze the binary representations of numbers. The substring "101" is a pattern within the binary digits. Instead of checking numbers one-by-one, you can model the binary numbers as strings and think about generating or recognizing all binary strings that contain the substring "101". This resembles a pattern matching or automaton problem.
Step 2: Automaton Construction
Build a finite automaton (state machine) that tracks the presence of the pattern "101" as you process bits from the most significant bit (MSB) to the least significant bit (LSB). This automaton will have states that represent how much of the pattern "101" has been matched so far. For example:
- State 0: no match yet
- State 1: matched '1'
- State 2: matched '10'
- State 3: matched '101' (final/accepting state)
Each bit added transitions the automaton to a new state depending on the current state and the bit value (0 or 1).
Step 3: Digit Dynamic Programming (DP) over Binary Representation
To count how many numbers less than or equal to N contain the pattern "101", you use a DP approach based on the binary digits of N and the automaton states. This approach is often called digit DP.
You keep track of:
- The current position in the binary representation (from MSB to LSB)
- The current automaton state (how much of "101" matched)
- Whether the prefix processed so far is exactly equal to the prefix of N or already smaller (to ensure you don't count numbers greater than N)
The DP returns the count of numbers up to N whose binary representation contains "101". If you do this efficiently, you can compute the count of lucky numbers ≤ N in O(number_of_bits × automaton_states) time, which is manageable for 64 bits and a small automaton.
Step 4: Counting Lucky Numbers in [L, R]
Using the function to count lucky numbers ≤ N, you can get:
countLucky(R) - countLucky(L-1) = number of lucky numbers in [L, R]
This allows you to check how many lucky numbers lie within your range.
Step 5: Finding the Kth Lucky Number
Since you can count lucky numbers up to any number N efficiently, you can perform a binary search on the range [L, R]:
- Define low = L and high = R
- At each step, pick mid = (low + high) // 2
- Compute countLucky(mid) - countLucky(L-1) = count of lucky numbers ≤ mid in the range
- If this count is ≥ K, it means the Kth lucky number lies at or before mid, so update high = mid
- Otherwise, update low = mid + 1
Continue until low meets high, which will be your Kth lucky number if it exists.
Step 6: Edge Cases and No Existence
If the total lucky numbers in [L, R] are less than K, print -1. Otherwise, the binary search will find the correct number.
Step 7: Implementation Details
- Convert numbers to binary strings to facilitate digit DP.
- Carefully implement the automaton transitions and the DP memoization.
- Handle leading zeros in binary representation correctly during DP to avoid counting invalid numbers.
- Optimize memory and computation by caching DP results.
Step 8: Summary
- Recognize the problem as counting numbers with a substring pattern in their binary form.
- Use automaton to track pattern matching states.
- Use digit DP to count how many numbers up to N contain the pattern.
- Use binary search over [L, R] with the counting function to find the Kth lucky number.
- Handle large inputs efficiently by avoiding brute force and relying on digit DP and automaton logic.
This method balances complexity and efficiency and is well-suited for very large ranges and K values due to the logarithmic binary search combined with polynomial-time DP counting.
```