Skip to content

3260. Find the Largest Palindrome Divisible by K

  • Time: $O(\log n)$
  • Space: $O(\log n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
 public:
  string largestPalindrome(int n, int k) {
    switch (k) {
      case 1:
        return string(n, '9');
      case 2:
        return n <= 2 ? string(n, '8') : "8" + string(n - 2, '9') + "8";
      case 3:
      case 9:
        return string(n, '9');
      case 4:
        return n <= 4 ? string(n, '8') : "88" + string(n - 4, '9') + "88";
      case 5:
        return n <= 2 ? string(n, '5') : "5" + string(n - 2, '9') + "5";
      case 6:
        if (n <= 2) {
          return string(n, '6');
        } else if (n % 2 == 1) {
          const int l = n / 2 - 1;
          return "8" + string(l, '9') + "8" + string(l, '9') + "8";
        } else {
          const int l = n / 2 - 2;
          return "8" + string(l, '9') + "77" + string(l, '9') + "8";
        }
      case 8:
        return n <= 6 ? string(n, '8') : "888" + string(n - 6, '9') + "888";
      default:
        const string middle[] = {"",          "7",          "77",
                                 "959",       "9779",       "99799",
                                 "999999",    "9994999",    "99944999",
                                 "999969999", "9999449999", "99999499999"};
        const int q = n / 12;
        const int r = n % 12;
        return string(q * 6, '9') + middle[r] + string(q * 6, '9');
    }
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution {
  public String largestPalindrome(int n, int k) {
    StringBuilder sb = new StringBuilder();

    switch (k) {
      case 1:
        return "9".repeat(n);
      case 2:
        return n <= 2 ? "8".repeat(n)
                      : sb.append("8") //
                            .append("9".repeat(n - 2))
                            .append("8")
                            .toString();
      case 3:
      case 9:
        return "9".repeat(n);
      case 4:
        return n <= 4 ? "8".repeat(n)
                      : sb.append("88") //
                            .append("9".repeat(n - 4))
                            .append("88")
                            .toString();
      case 5:
        return n <= 2 ? "5".repeat(n)
                      : sb.append("5") //
                            .append("9".repeat(n - 2))
                            .append("5")
                            .toString();
      case 6:
        if (n <= 2) {
          return "6".repeat(n);
        } else if (n % 2 == 1) {
          final int l = n / 2 - 1;
          return sb.append("8")
              .append("9".repeat(l))
              .append("8")
              .append("9".repeat(l))
              .append("8")
              .toString();
        } else {
          final int l = n / 2 - 2;
          return sb.append("8")
              .append("9".repeat(l))
              .append("77")
              .append("9".repeat(l))
              .append("8")
              .toString();
        }
      case 8:
        return n <= 6 ? "8".repeat(n)
                      : sb.append("888") //
                            .append("9".repeat(n - 6))
                            .append("888")
                            .toString();
      default:
        String[] middle = {"",         "7",         "77",         "959",
                           "9779",     "99799",     "999999",     "9994999",
                           "99944999", "999969999", "9999449999", "99999499999"};
        final int q = n / 12;
        final int r = n % 12;
        return sb.append("999999".repeat(q))
            .append(middle[r])
            .append("999999".repeat(q))
            .toString();
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
  def largestPalindrome(self, n: int, k: int) -> str:
    match k:
      case 1:
        return '9' * n
      case 2:
        return '8' * n if n <= 2 else '8' + '9' * (n - 2) + '8'
      case 3 | 9:
        return '9' * n
      case 4:
        return '8' * n if n <= 4 else '88' + '9' * (n - 4) + '88'
      case 5:
        return '5' * n if n <= 2 else '5' + '9' * (n - 2) + '5'
      case 6:
        if n <= 2:
          return '6' * n
        elif n % 2 == 1:
          l = n // 2 - 1
          return '8' + '9' * l + '8' + '9' * l + '8'
        else:
          l = n // 2 - 2
          return '8' + '9' * l + '77' + '9' * l + '8'
      case 8:
        return '8' * n if n <= 6 else '888' + '9' * (n - 6) + '888'
      case _:
        middle = {
            0: '', 1: '7', 2: '77', 3: '959', 4: '9779', 5: '99799',
            6: '999999', 7: '9994999', 8: '99944999', 9: '999969999',
            10: '9999449999', 11: '99999499999'
        }
        q, r = divmod(n, 12)
        return '999999' * q + middle[r] + '999999' * q