# Project Euler #51: Prime digit replacements

# Project Euler #51: Prime digit replacements

kitchent + 0 comments Took me some time to realise the output of

`5 1 2`

is`10007 10009`

instead of`10007 10037`

(Python, it gave wrong answer for Test #3 and #10).Was trying to save time by returning the first plausible result from digit replacement generated by looping through digits from

`0`

to`9`

, and it turns out that way it's not necessarily the minimum result.Eventually I computed all plausible results from all digit replacement and its corresponding permutations. I would say it's too ugly to my taste.

**EDIT**: Made use of generator combining permutations with`deque()`

to`yield`

the next smallest replacement position, so it does not have to generate the whole thing in advance. Sounds simple, troublesome to implement. The slowest time for me is 4.74s for #18. Previous version took almost 8s...

anil2381 + 0 comments test cases are weak. for input 3 2 1 my solution is giving output 113, but it should be 101.

Akul_Swamy + 2 comments Hey, I seem to be getting WA for cases 7 and 8 only. Any boundary cases that I need to be careful about?

armogur + 1 comment same here, still not getting the issue ...

NiakTheWizard + 1 comment Make sure the number you're currently considering is actually in the set that you print, otherwise you might output a non-minimal solution...

remidinishanth + 0 comments Thanks very much, this saved me.

PhilippH + 0 comments Try

Input:

7 4 6

Output:

2422027 3433037 5455057 6466067 8488087 9499097

agutowski + 2 comments Am I missing something, or for sample input #01 (2 1 3) there are many possible answers? ((11, 13, 17), (11, 13, 19), (11, 31, 41), (11, 31, 61) and so on)

If so, how should we decide which solution to choose?

shashank21jHackerRank AdminChallenge Author + 1 comment The minimalistic set. Say 11 is smallest for 3 length family, then compare on second number and so on.

metaflow + 0 comments please fix the description to address this

ankur22388 + 1 comment You have to actually consider those numbers only which gives only 3 prime numbers if arranged as per the input conditions. Like if you are considering (11,13,17) by fixing 1 and replacing 2nd digit with some number will also give 19 as prime number. So it will be considered for L as 4 but the input is 3.

cantonios + 0 comments Then why does it say, "Print the first L numbers of the prime value family"?

That seems to suggest the family can be larger than L, but it only wants you to print the first L.

khoangcachxalam1 + 0 comments finally , i finish ;) ,, this problem is very good 8 4 7 80047003 81147113 83347333 84447443 86647663 87747773 89947993 .. i like this problem, the first , i build prime <=100000000 ,, then i use dfs to creat all permutation ,, then , use them to test all prime in condition n ,,

vpinmrcool + 0 comments Can someone please tell what is Test Case 16.

vpinmrcool + 0 comments I've all tests but Test Case 16. Can someone suggest any way to reduce number of primes we scan or choosing k from n digits.

andres_jaanson + 0 comments Really liked the problem. But for the one test case which is 7 1 ? I had to cheat a bit. I am using JAVA and in the test environment I got the test passing in 2.8 seconds although sometimes it also timedout but in grading it timedout every time.

I had rewritten a lot of logic just for the one test case yet it still was not enough. As I had no ideas on how to improve more. Based on the answer from test environment for 7 1 I just limited the prime count to be analysed. That enabled me to pass the case.

IvarRasmus + 0 comments Did it with python3 and really had to squeeze everything out to get it under time. However, interesting to note that only about 25% of the time was spent in divisibility tests. A lot of little stuff was killing me, binary search and sorting, and both could probably be eliminated. I think you could get close to 1 second on 18 and 19 in C.

Crafter_Artisan + 0 comments (a) Prime sieve up to 10^7

(b) Look for primes nearest to 10^(N - 1) and go up

(c) Assemble masks by recursion, ensuring along the way that all replaced digits are equal

Sort 15 Discussions, By:

Please Login in order to post a comment