TLE: 132/632

blog_deepseek_v3_0324_coding_lc_question_response.cpp

#include <string>
#include <algorithm>

using namespace std;

class Solution {
public:
    string largestPalindrome(int n, int k) {
        if (n == 1) {
            // The largest 1-digit palindrome divisible by k is the largest digit (9) or less, which is a multiple of k.
            int max_num = 9;
            while (max_num > 0 && max_num % k != 0) {
                max_num--;
            }
            return to_string(max_num);
        }
        
        // Construct the largest possible palindrome of n digits.
        string max_palindrome;
        string first_half;
        for (int i = 0; i < n; ++i) {
            first_half += '9';
        }
        bool found = false;
        string result;
        
        // We need to find the largest palindrome <= first_half (which is 999...n times) and divisible by k.
        // The first step is to generate the largest palindrome with n digits.
        // Generate palindromes in descending order and check for divisibility.
        
        // Construct the maximum possible palindrome. For n digits: e.g., n=3: 999 -> check if 999 is divisible by k; else 989, 979 ... down to 101 or until find one divisible by k.
        // But checking every number down from 10^n -1 to 10^(n-1) is impractical for large n (1e5 digits).
        // Instead, generate the largest palindromes by mirroring the first half.
        
        // So for large n (like n is 1e5), even generating the full palindrome as a string is necessary.
        // So solution involves creating the largest palindrome possible, then checking divisibility by k, and if not, trying the next smaller palindrome.
        // The largest possible n-digit number is 10^n - 1. The largest possible palindrome is mirroring half.
        
        string upperHalf = string(n / 2, '9');
        if (n % 2 == 1) {
            upperHalf = string(n / 2 + 1, '9');
        }
        
        while (true) {
            // Construct the full palindrome based on upperHalf.
            string palindrome;
            if (n % 2 == 0) {
                string second_half = upperHalf;
                reverse(second_half.begin(), second_half.end());
                palindrome = upperHalf + second_half;
            } else {
                string second_half = upperHalf.substr(0, upperHalf.size() - 1);
                reverse(second_half.begin(), second_half.end());
                palindrome = upperHalf + second_half;
            }
            
            // Check if the number is divisible by k. However, the number can be very large (n up to 1e5) so doing mod directly is problematic.
            // Thus, we can compute mod k by processing the string number digit by digit.
            if (isDivisible(palindrome, k)) {
                return palindrome;
            }
            
            // Decrease the upperHalf by 1.
            if (!decrement(upperHalf)) {
                break; // upperHalf has become all zeros, which means numbers ниже are leading zero or invalid.
            }
        }
        
        return "";
    }
    
private:
    bool isDivisible(const string &num, int k) {
        long long remainder = 0;
        for (char c : num) {
            int digit = c - '0';
            remainder = (remainder * 10 + digit) % k;
        }
        return remainder == 0;
    }
    
    bool decrement(string &s) {
        int n = s.length();
        int i = n - 1;
        while (i >= 0 && s[i] == '0') {
            s[i] = '9';
            i--;
        }
        if (i < 0) {
            return false;
        }
        s[i]--;
        return true;
    }
};

Problem Link: https://leetcode.com/problems/find-the-largest-palindrome-divisible-by-k/