Lucky Numbers

4.6

7 votes
Algorithms, Dynamic Programming, Introduction to Dynamic Programming 1
Problem

Let us call a number a lucky number if all the digits in the number are odd.

Given a number N , Alice wonders what is the nearest lucky number to N.

Find a number X such that abs(NX) is minimum and X is a lucky number.

Input Format:

First line contains an integer N

Output Format:

Print an integer X such that abs(NX) is minimum
Incase of multiple answers, print the smallest answer

Constraints:
1N1018

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Nearest Lucky Numbers to 6, with all digits odd are 5 and 7 with abs(6-5) = abs(6-7) = 1

But since 5 is the smallest answer, print 5

Editor Image

?