Welcome to Subscribe On Youtube

2081. Sum of k-Mirror Numbers

Description

A k-mirror number is a positive integer without leading zeros that reads the same both forward and backward in base-10 as well as in base-k.

  • For example, 9 is a 2-mirror number. The representation of 9 in base-10 and base-2 are 9 and 1001 respectively, which read the same both forward and backward.
  • On the contrary, 4 is not a 2-mirror number. The representation of 4 in base-2 is 100, which does not read the same both forward and backward.

Given the base k and the number n, return the sum of the n smallest k-mirror numbers.

 

Example 1:

Input: k = 2, n = 5
Output: 25
Explanation:
The 5 smallest 2-mirror numbers and their representations in base-2 are listed as follows:
  base-10    base-2
    1          1
    3          11
    5          101
    7          111
    9          1001
Their sum = 1 + 3 + 5 + 7 + 9 = 25. 

Example 2:

Input: k = 3, n = 7
Output: 499
Explanation:
The 7 smallest 3-mirror numbers are and their representations in base-3 are listed as follows:
  base-10    base-3
    1          1
    2          2
    4          11
    8          22
    121        11111
    151        12121
    212        21212
Their sum = 1 + 2 + 4 + 8 + 121 + 151 + 212 = 499.

Example 3:

Input: k = 7, n = 17
Output: 20379000
Explanation: The 17 smallest 7-mirror numbers are:
1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596

 

Constraints:

  • 2 <= k <= 9
  • 1 <= n <= 30

Solutions

  • class Solution {
        public long kMirror(int k, int n) {
            long ans = 0;
            for (int l = 1;; ++l) {
                int x = (int) Math.pow(10, (l - 1) / 2);
                int y = (int) Math.pow(10, (l + 1) / 2);
                for (int i = x; i < y; i++) {
                    long v = i;
                    for (int j = l % 2 == 0 ? i : i / 10; j > 0; j /= 10) {
                        v = v * 10 + j % 10;
                    }
                    String ss = Long.toString(v, k);
                    if (check(ss.toCharArray())) {
                        ans += v;
                        if (--n == 0) {
                            return ans;
                        }
                    }
                }
            }
        }
    
        private boolean check(char[] c) {
            for (int i = 0, j = c.length - 1; i < j; i++, j--) {
                if (c[i] != c[j]) {
                    return false;
                }
            }
            return true;
        }
    }
    
  • class Solution {
    public:
        long long kMirror(int k, int n) {
            long long ans = 0;
            for (int l = 1;; ++l) {
                int x = pow(10, (l - 1) / 2);
                int y = pow(10, (l + 1) / 2);
                for (int i = x; i < y; ++i) {
                    long long v = i;
                    int j = (l % 2 == 0) ? i : i / 10;
                    while (j > 0) {
                        v = v * 10 + j % 10;
                        j /= 10;
                    }
                    if (check(v, k)) {
                        ans += v;
                        if (--n == 0) {
                            return ans;
                        }
                    }
                }
            }
        }
    
    private:
        bool check(long long x, int k) {
            vector<int> s;
            while (x > 0) {
                s.push_back(x % k);
                x /= k;
            }
            for (int i = 0, j = s.size() - 1; i < j; ++i, --j) {
                if (s[i] != s[j]) {
                    return false;
                }
            }
            return true;
        }
    };
    
    
  • class Solution:
        def kMirror(self, k: int, n: int) -> int:
            def check(x: int, k: int) -> bool:
                s = []
                while x:
                    s.append(x % k)
                    x //= k
                return s == s[::-1]
    
            ans = 0
            for l in count(1):
                x = 10 ** ((l - 1) // 2)
                y = 10 ** ((l + 1) // 2)
                for i in range(x, y):
                    v = i
                    j = i if l % 2 == 0 else i // 10
                    while j > 0:
                        v = v * 10 + j % 10
                        j //= 10
                    if check(v, k):
                        ans += v
                        n -= 1
                        if n == 0:
                            return ans
    
    
  • func kMirror(k int, n int) int64 {
    	check := func(x int64, k int) bool {
    		s := []int{}
    		for x > 0 {
    			s = append(s, int(x%int64(k)))
    			x /= int64(k)
    		}
    		for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
    			if s[i] != s[j] {
    				return false
    			}
    		}
    		return true
    	}
    
    	var ans int64 = 0
    	for l := 1; ; l++ {
    		x := pow10((l - 1) / 2)
    		y := pow10((l + 1) / 2)
    		for i := x; i < y; i++ {
    			v := int64(i)
    			j := i
    			if l%2 != 0 {
    				j = i / 10
    			}
    			for j > 0 {
    				v = v*10 + int64(j%10)
    				j /= 10
    			}
    			if check(v, k) {
    				ans += v
    				n--
    				if n == 0 {
    					return ans
    				}
    			}
    		}
    	}
    }
    
    func pow10(exp int) int {
    	res := 1
    	for i := 0; i < exp; i++ {
    		res *= 10
    	}
    	return res
    }
    
    
  • function kMirror(k: number, n: number): number {
        function check(x: number, k: number): boolean {
            const s: number[] = [];
            while (x > 0) {
                s.push(x % k);
                x = Math.floor(x / k);
            }
            for (let i = 0, j = s.length - 1; i < j; i++, j--) {
                if (s[i] !== s[j]) {
                    return false;
                }
            }
            return true;
        }
    
        let ans = 0;
        for (let l = 1; ; l++) {
            const x = Math.pow(10, Math.floor((l - 1) / 2));
            const y = Math.pow(10, Math.floor((l + 1) / 2));
            for (let i = x; i < y; i++) {
                let v = i;
                let j = l % 2 === 0 ? i : Math.floor(i / 10);
                while (j > 0) {
                    v = v * 10 + (j % 10);
                    j = Math.floor(j / 10);
                }
                if (check(v, k)) {
                    ans += v;
                    n--;
                    if (n === 0) {
                        return ans;
                    }
                }
            }
        }
    }
    
    

All Problems

All Solutions