Palindrometer
InterviewTime limit1sMemory limit128 MB
Given an odometer reading with fixed digit positions, find the smallest number of kilometers to drive until it reads as a palindrome, counting leading zeros.
- Level
Medium5 of 10
- Topics
- String, Math, Greedy, Implementation
- Solved
- No attempts yet
Problem
Seunghwan loves palindromes: numbers that read the same forwards and backwards. Right now his car's odometer reads 100000. After driving just 1 more kilometer it will read 100001, which is a palindrome!
Given the number currently shown on the odometer, write a program that finds how many more kilometers he must drive until it reads a palindrome. Every digit position shown on the odometer must take part in the palindrome, INCLUDING the leading zeros. So a reading of 00121 is not a palindrome.
Input
The input consists of several test cases. Each test case is a single line holding the number currently shown on the odometer. This number has between 2 and 9 digits, inclusive. The odometer shows exactly as many digit positions as the given number has, so an input of 00456 is a 5-digit reading. The last line contains a single 0.
Output
For each test case, output the minimum distance Seunghwan must drive for the odometer to read a palindrome. If it is already a palindrome, output 0.