LUCKYNUM - Editorial spoj

editorial
, , , ,
1

(Question) In some Asian countries, 8 and 6 are considered lucky digits. Any number containing only 8s and 6s is considered lucky number, e.g. 6, 8, 66, 668, 88, 886 … Nguyen is a student who likes mathematics very much. Nguyen likes lucky numbers but only of the form

S = 8…86…6

where S has at least one digit and the number of 8s or 6s can be zero. Examples of S are 8, 88, 6, 66, 86, 886, 8866 …

Given a positive integer X (1 < X < 10 000), Nguyen wants to find the smallest lucky number S which has at most 200 digits and is divisible by X.

Your task is to write a program to find that number for Nguyen.

problem link: Contest Page | CodeChef , http://www.spoj.com/problems/LUCKYNUM/

someone please provide the logic or the code

2

Since you only asked for algo, I think this will be appropriate. Get back to me in case you need further help!

Algo

EDIT: A more detailed solution provided here

(PS: I found problem similar to SPOJ’s Zero and One. I did not link you to solution of your problem, but solution of a similar problem which uses same algo. I hope it would help. In case it doesn’t, get back to me, k?)

3

do you have the code for this problem?

4

@amin

I am reluctant to give full code to the problem, cause I think you CAN solve it.

I will give code for SPOJ problem. You see that, and then with based on the concept learnt, try again. If you fail after that, I will give you the code. But try one more time!! :slight_smile: :slight_smile:

Code 1 Code 2

(Hint: Problems are very similar, only numbers changed)

EDIT 2 - Anyways, I believe you’d be honest in solving , so here is the answer code. See It only if you get absolutely clueless on how to proceed, k?

Answer Another good code

5

just noticed that 68, 688,668 … are not in the set S.
thanks anyway

6

First of all tell me about your concept in BFS, DFS or in simply looping? Are u fully aware of all these?

7

i didn’t read the question properly. i thought the answer for n=34 would be 68, but 68 is not in the set S. now, i have solved it. Yeah, i was doing bfs and generating all the possible lucky numbers 6,8,66,68,86,88,666, … (2^200 -1 terms) and checking the divisibility.