Yeah because i guess we would have to find all possible combinations from the numbers at hand , and at worst case there could be more than n! combinations
His question is practically wrong and has no solution,
you said string can be of the length 10000000.
Means the prime number can have 10^7 digits as well.
To check if such a big number which has 10^7 or more digits…is prime or not…is out of the scope of computer science.
Kudos to the interviewer! 
3 Likes
lol ok ,
But theoretically speaking, please still let me know what could bet the best possible solution.
Thanks!
If the string length is more than 15-16, there exists no solution …as you can never know that a number as great as 10^16 is prime or not without the compiler going mad.
The obvious solution is simple brute-force + sieve 
for string-length< 15
1 Like
There are methods to check huge numbers are prime or not.
Your reply Should be “it’s impossible”
Theoretically or practically 
10^7 digits will have 2^(10^7) numbers.
And how will you iterate 2^(10^7) values ?
I think you interviewer was kidding with you and wanted to check if you know big O notation and capacity of any normal Computer.
Say, I have to check numbers with 10^6 digits…if they are prime or not, can you check such 10 numbers in under 0.5 second? Good
I wish I was as high as the interviewer
1 Like
Let me know that too
Say, the question is find all the different prime numbers from the string by taking the subsets…
But prime number should always be less than 10.
Solution:-Just count the occurrence of 2,3,5,7 and that is your answer.
For prime<100, its easy to calculate it, @l_returns God will tell you for sure
1 Like
Prime number - Wikipedia
Check primality tests.
And I never said it’s possible with 10^6 digits.
You said it’s not possible for values are greater than 10^15 or 10^16 
What I am saying is it’s not correct.
Nope we won’t
Find it on your own
Since you don’t have any proof of source 
1 Like
What ? How ?
I don’t know how to solve even if string length is 14 
( in 0.5 sec)
1 Like
I though pollard rho would help.
Conclusion:- Interviewer is super high and we should be like him 
1 Like
it isnt an ongoing contest , that i can assure you of. I have done that mistake before, wont do it again
1 Like
Okay \hspace{0mm}
1 Like
Yeah people asking doubt about contest say that it’s not from ongoing.
I have this experience on discuss itself
I asked him that if it’s not from an ongoing. He said “I can assure it’s not from ongoing” and next day someone confirmed that it was from ongoing.
1 Like
Ye duniyaa hai Kala Bazaar…
1 Like
discussion me chat kar kar ke top contributors ban jao frands.
PS: count me in