LUCKYNUM - Editorial spoj

(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: https://www.codechef.com/problems/P10 , http://www.spoj.com/problems/LUCKYNUM/

someone please provide the logic or the code

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?)

@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

do you have the code for this problem?

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

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

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.