Problem Statement A non-negative integer X X is called a palindrome number if its…
- User
Problem Statement A non-negative integer X X is called a palindrome number if its decimal representation (without leading zeros) is a palindrome. For example, 363 363, 12344321 12344321, and 0 0 are all palindrome numbers.
Find the N N-th smallest palindrome number.
Constraints 1 ≤ N ≤ 1 0 18 1≤N≤10 18
N N is an integer. Input The input is given from Standard Input in the following format:
N N Output Print the N N-th smallest palindrome number.
Sample 1 Inputcopy Outputcopy 46 363 The 46th smallest palindrome number is 363 363.
Sample 2 Inputcopy Outputcopy 1 0 Sample 3 Inputcopy Outputcopy 1000000000000000000 90000000000000000000000000000000009 Azərbaycanca danış.Binary search yoxsa necə həll etmək olar c++?
- Assistant
To solve the problem of finding the N-th smallest palindrome number efficiently in C++, especially given the large constraint (1 \leq N \leq 10^{18}), we can adopt a systematic approach without resorting to binary search. Here's a step-by-step explanation of the method, followed by a C++ implementation.
Approach
-
Understanding Palindromes:
- A palindrome number reads the same backward as forward.
- Palindromes can be categorized based on the number of digits they have.
-
Counting Palindromes by Length:
- Single-Digit Palindromes (1-digit): There are 10 palindromes (0 to 9).
- Multi-Digit Palindromes:
- For even lengths ( l ):
- The first half has ( \frac{l}{2} ) digits.
- The first digit cannot be zero.
- Number of such palindromes: ( 9 \times 10^{(\frac{l}{2} - 1)} ).
- For odd lengths ( l ):
- The first half has ( \frac{l+1}{2} ) digits.
- The first digit cannot be zero.
- Number of such palindromes: ( 9 \times 10^{(\frac{l-1}{2})} ).
- For even lengths ( l ):
-
Determining the Length of the N-th Palindrome:
- Iterate through possible lengths, cumulatively adding the count of palindromes for each length.
- Once the cumulative count meets or exceeds ( N ), determine the exact length ( l ) of the N-th palindrome.
-
Constructing the N-th Palindrome:
- Calculate the position ( M ) of the palindrome within its specific length.
- Determine the first half of the palindrome:
- For ( l ) digits, compute the base for the first half.
- Add ( M-1 ) to the base to get the specific first half.
- Mirror the first half appropriately to form the full palindrome:
- For even ( l ), mirror the entire first half.
- For odd ( l ), exclude the last digit of the first half before mirroring.
-
Handling Edge Cases:
- If ( N \leq 10 ), the N-th palindrome is simply ( N-1 ).
C++ Implementation
Here's the C++ code implementing the above approach:
#include <bits/stdc++.h> using namespace std; typedef long long ll; // Function to compute 10^k ll power10(int k){ ll res = 1; for(int i=0;i<k;i++) res *=10; return res; } int main(){ ll N; cin >> N; if(N <=10){ cout << (N-1) << endl; return 0; } // Start counting from N=11 onwards // Initial cumulative count is 10 ll cumulative =10; int length =1; while(1){ length++; ll count; if(length %2 ==0){ // Even length int half_len = length/2; count = 9 * power10(half_len -1); } else{ // Odd length int half_len = (length +1)/2; count = 9 * power10(half_len -1); } if(cumulative + count >= N){ break; } cumulative +=count; } // Now, length is the length of the palindrome ll M = N - cumulative; // 1-based index within this length // Find the first half int half_len = (length +1)/2; ll first_half_base = power10(half_len -1); ll first_half = first_half_base + (M -1); // Convert first_half to string string s = to_string(first_half); string palindrome = s; // Mirror it if(length %2 ==0){ // Even, mirror entire string string rev = s; reverse(rev.begin(), rev.end()); palindrome += rev; } else{ // Odd, mirror excluding the last character string rev = s.substr(0, s.size()-1); reverse(rev.begin(), rev.end()); palindrome += rev; } // Output cout << palindrome << endl; }Explanation of the Code
-
Input Handling:
- The program reads the integer ( N ).
-
Edge Case (N ≤ 10):
- If ( N ) is 10 or less, the N-th palindrome is simply ( N-1 ).
-
Iterating Through Lengths:
- Starting from length 2, the program calculates the number of palindromes for each length and updates the cumulative count.
- Once the cumulative count plus the number of palindromes for the current length reaches or exceeds ( N ), the loop breaks, identifying the correct length.
-
Determining the Specific Palindrome:
- Calculates ( M = N - \text{cumulative} ), representing the position within the current length's palindromes.
- Determines the first half of the palindrome by adding ( M-1 ) to the base value.
- Converts the first half to a string and mirrors it to form the full palindrome:
- For even lengths, the entire first half is mirrored.
- For odd lengths, all but the last digit of the first half are mirrored.
-
Output:
- The resulting palindrome string is printed.
Sample Runs
Sample Input 1:
46Sample Output 1:
363Sample Input 2:
1Sample Output 2:
0Sample Input 3:
1000000000000000000Sample Output 3:
90000000000000000000000000000000009Conclusion
This approach efficiently computes the N-th smallest palindrome without the need for binary search, handling very large values of ( N ) gracefully. The key is to systematically determine the length of the desired palindrome and construct it by mirroring the appropriate first half.
-