Sum of k-Mirror Numbers

 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

class Solution {
public:
   long long kMirror(int k, int n) {
      vector<long long> ans;
      for (int len = 1; ans.size() < n; ++len) {
        for (int half = pow(10, (len - 1) / 2); half < pow(10, (len + 1) / 2) && ans.size() < n; ++half) {
           string s = to_string(half);
           string rev = s;
           reverse(rev.begin(), rev.end());
           string pal = s + rev.substr(len % 2);
           long long num = stoll(pal);
           vector<int> basek;
           long long tmp = num;
           while (tmp) {
              basek.push_back(tmp % k);
              tmp /= k;
           }
           if (equal(basek.begin(), basek.end(), basek.rbegin()))
              ans.push_back(num);
        }
      }
      long long sum = 0;
      for (auto x : ans) sum += x;
      return sum;
   }
};

 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

func kMirror(k int, n int) int64 {
   ans := []int64{}
   for l := 1; len(ans) < n; l++ {
      start := intPow(10, (l-1)/2)
      end := intPow(10, (l+1)/2)
      for half := start; half < end && len(ans) < n; half++ {
        s := strconv.Itoa(half)
        rev := reverseStr(s)
        pal := s + rev
        if l%2 == 1 {
           pal = s + rev[1:]
        }
        num, _ := strconv.ParseInt(pal, 10, 64)
        if isPalindrome(baseK(num, k)) {
           ans = append(ans, num)
        }
      }
   }
   var sum int64
   for _, v := range ans {
      sum += v
   }
   return sum
}

func intPow(a, b int) int {
   res := 1
   for b > 0 {
      res *= a
      b--
   }
   return res
}

func reverseStr(s string) string {
   b := []byte(s)
   for i, j := 0, len(b)-1; i < j; i, j = i+1, j-1 {
      b[i], b[j] = b[j], b[i]
   }
   return string(b)
}

func baseK(num int64, k int) []int {
   res := []int{}
   for num > 0 {
      res = append(res, int(num%int64(k)))
      num /= int64(k)
   }
   return res
}

func isPalindrome(arr []int) bool {
   for i, j := 0, len(arr)-1; i < j; i, j = i+1, j-1 {
      if arr[i] != arr[j] {
        return false
      }
   }
   return true
}

 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 {
   public long kMirror(int k, int n) {
      List<Long> ans = new ArrayList<>();
      for (int len = 1; ans.size() < n; ++len) {
        int start = (int)Math.pow(10, (len - 1) / 2);
        int end = (int)Math.pow(10, (len + 1) / 2);
        for (int half = start; half < end && ans.size() < n; ++half) {
           String s = Integer.toString(half);
           StringBuilder rev = new StringBuilder(s).reverse();
           String pal = s + rev.substring(len % 2);
           long num = Long.parseLong(pal);
           if (isKPalindrome(num, k)) {
              ans.add(num);
           }
        }
      }
      long sum = 0;
      for (long x : ans) sum += x;
      return sum;
   }
   private boolean isKPalindrome(long num, int k) {
      List<Integer> digits = new ArrayList<>();
      while (num > 0) {
        digits.add((int)(num % k));
        num /= k;
      }
      for (int i = 0, j = digits.size() - 1; i < j; ++i, --j) {
        if (!digits.get(i).equals(digits.get(j))) return false;
      }
      return true;
   }
}

 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

class Solution {
   fun kMirror(k: Int, n: Int): Long {
      val ans = mutableListOf<Long>()
      var len = 1
      while (ans.size < n) {
        val start = Math.pow(10.0, ((len - 1) / 2).toDouble()).toInt()
        val end = Math.pow(10.0, ((len + 1) / 2).toDouble()).toInt()
        for (half in start until end) {
           if (ans.size >= n) break
           val s = half.toString()
           val rev = s.reversed()
           val pal = s + rev.substring(len % 2)
           val num = pal.toLong()
           if (isKPalindrome(num, k)) {
              ans.add(num)
           }
        }
        len++
      }
      return ans.sum()
   }
   private fun isKPalindrome(num: Long, k: Int): Boolean {
      val digits = mutableListOf<Int>()
      var n = num
      while (n > 0) {
        digits.add((n % k).toInt())
        n /= k
      }
      return digits == digits.reversed()
   }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
   def kMirror(self, k: int, n: int) -> int:
      def is_k_palindrome(x: int) -> bool:
        arr = []
        while x:
           arr.append(x % k)
           x //= k
        return arr == arr[::-1]

      ans: list[int] = []
      length = 1
      while len(ans) < n:
        for half in range(10 ** ((length - 1) // 2), 10 ** ((length + 1) // 2)):
           s = str(half)
           pal = s + s[-2::-1] if length % 2 else s + s[::-1]
           num = int(pal)
           if is_k_palindrome(num):
              ans.append(num)
           if len(ans) == n:
              break
        length += 1
      return sum(ans)

 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

impl Solution {
   pub fn k_mirror(k: i32, n: i32) -> i64 {
      fn is_k_palindrome(mut x: i64, k: i32) -> bool {
        let mut arr = vec![];
        while x > 0 {
           arr.push((x % k as i64) as i32);
           x /= k as i64;
        }
        arr.iter().eq(arr.iter().rev())
      }
      let mut ans = vec![];
      let mut len = 1;
      while ans.len() < n as usize {
        let start = 10_i64.pow(((len - 1) / 2) as u32);
        let end = 10_i64.pow(((len + 1) / 2) as u32);
        for half in start..end {
           let s = half.to_string();
           let pal = if len % 2 == 0 {
              format!("{}{}", s, s.chars().rev().collect::<String>())
           } else {
              format!("{}{}", s, s.chars().rev().skip(1).collect::<String>())
           };
           let num = pal.parse::<i64>().unwrap();
           if is_k_palindrome(num, k) {
              ans.push(num);
           }
           if ans.len() == n as usize {
              break;
           }
        }
        len += 1;
      }
      ans.iter().sum()
   }
}