All challenges
Easy 0 solved 0% acceptance

Double-Base Palindromes

Add up the numbers that read the same both ways in base 10 and in a second base.

What you'll learn

  • Convert a number to any base
  • Check whether a sequence is a palindrome
  • Combine two conditions cheaply

Problem

A palindrome reads the same forwards and backwards. 33 is a palindrome in base 10, and in base 2 it is 100001, a palindrome again. Add up every number from 1 to limit that is a palindrome both in base 10 and in base base. Numbers are written without leading zeros.

Implement double_base_palindromes(limit, base).

Input

limit: The largest number to check.

base: The second base.

Output

Return the sum of all such numbers.

Constraints

1 ≤ limit ≤ 100,000; 2 ≤ base ≤ 16

Examples

Example 1
Input:
limit = 10
base = 2

Expected output:
expected = 25
Input:
long long limit = 10;
long long base = 2;

Expected output:
long long expected = 25;
Input:
long limit = 10;
long base = 2;

Expected output:
long expected = 25;

Explanation

1, 3, 5, 7 and 9 are 1, 11, 101, 111 and 1001 in base 2, all palindromes; 2, 4, 6 and 8 are not. Sum 25.

Example 2
Input:
limit = 50
base = 3

Expected output:
expected = 15
Input:
long long limit = 50;
long long base = 3;

Expected output:
long long expected = 15;
Input:
long limit = 50;
long base = 3;

Expected output:
long expected = 15;

Explanation

In base 3: 1, 2, 4 (11) and 8 (22) qualify, while 33 is 1020 and 44 is 1122. Sum 15.

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

Repeated division by the base gives the digits from last to first.

Hint 2

A palindrome check compares the digit list with its reverse.

Hint 3

Check base 10 first: few numbers pass it, so the second conversion is rarely needed.

Expected complexity

O(limit × log limit) time, O(log limit) extra space

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.