PrimeWithSubstring
SRM 774 · 2020-01-09 · by misof
Problem Statement
Jaro has a favorite number: the non-negative integer N.
Jaro would also like to have a favorite prime number. But remembering new numbers is hard. Thus, the prime number must be reasonably small and it must contain his favorite number.
Find and return any
- X is a prime.
- X must have at most 12 digits.
- When written out in base 10, the digits of X must contain the digits of N as a contiguous substring.
Notes
- It is guaranteed that each valid input has a solution. Any valid solution will be accepted.
- Primes are positive integers with exactly two positive integer divisors. The smallest few primes are 2, 3, 5, 7, 11, 13, 17, ...
- The numbers 0 and 1 are not primes.
Constraints
- N will be between 0 and 10^9, inclusive.
47 Returns: 47
The number itself is a prime, so Jaro is in luck.
42 Returns: 15427
The number 15427 is prime, it is small enough, and "15427" does contain "42", so this is a valid answer. Note that, for example, 4021 is not a valid answer: it is a small prime, but "4021" does not contain "42".
0 Returns: 4021
Now 4021 is a perfectly acceptable answer.
123456789 Returns: 312345678971
Watch out for integer overflow, the answers are sometimes too big for a 32-bit data type.
111 Returns: 2111
1000000000 Returns: 100000000003
This is the largest possible input.
Submissions are judged against all 128 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PrimeWithSubstring with a public method long long findPrime(int N) · 128 test cases · 2 s / 256 MB per case