[Deloitte OA] 7th Nearest Palindrome | Optimal C++ Solution | Precompute + Binary Search
- Posted
- 12 May 2026
Summary
I encountered a challenging online assessment problem where I had to find the 7th nearest palindrome to a given number efficiently.
How it went
During my Online Assessment with Deloitte for the Analyst position, I was presented with an intriguing algorithmic challenge involving palindromes.
The task required finding the 7th nearest palindrome to a given integer $ N $ (where $ N \le 10^9 $), under specific constraints:
- Single-digit numbers are not considered palindromes.
- Distance is calculated as absolute difference $|P - N|$.
- In case of equal distances, the larger palindrome is preferred.
To tackle this efficiently within a strict time limit of 1 second across multiple test cases, I employed a two-phase strategy:
- Precomputation: Generated all valid palindromes up to $10^{10}$ in advance using prefix-based generation. This resulted in around ~110,000 palindromes which were stored globally and sorted once.
- Query-Time Optimization: For each query, used binary search (`std::lower_bound`) to locate the closest palindromes and examined a small window (+/- 20 elements). Then, I re-sorted just that window according to our custom distance rules to identify the 7th nearest palindrome quickly.
Questions asked (1)
- 01
Find 7th Nearest Palindrome
Data Structures & Algorithms · Hard
Given an integer $ N $ (where $ N \le 10^9 $), find the 7th nearest palindrome to $ N $.
Constraints:
- Single-digit numbers (1–9) are not considered palindromes.
- Distance is defined as the absolute difference: $ |P - N| $.
- If two palindromes have the same distance, prefer the larger one.
- Multiple queries may be processed; optimize accordingly.
Example:
Input: N = 100 Output: [Depends on generated palindromes near 100]
How they prepared
I prepared by reviewing advanced techniques in competitive programming related to number theory and optimized searching/sorting strategies. Specifically focused on:
- Palindrome generation algorithms.
- Binary search applications beyond simple lookup.
- Custom comparators in sorting functions.
- Efficient preprocessing for batch-query scenarios.