Another application of MRP with caching. The caveat here is that using BigInteger implementation of MRP Test leads to TLE. Converting to Long does the trick. There is still usage of BigInteger for modular exponentiation (otherwise you’d have to implement your own, which can be a little tricky), but that doesn’t seem to add much overhead to the solution.
It is also interesting to use OpenAI ChatGPT 4.0 model to ask and learn for the detailed time complexity of this algorithm. It is amazing to see how fast MPR is – an impressive LogN. Answer from the bot is down below, as well s my code. Cheers, ACC.
Analysis from OpenAI ChatGPT Model 4.0:
Time Complexity:
🔸 Worst Case: O(n² log m)
(where m is the largest number formed from the substring)
🔸 With caching and typical inputs, it behaves closer to O(n²).
Sum of Largest Prime Substrings – LeetCode
Given a string s, find the sum of the 3 largest unique that can be formed using any of its .
Return the sum of the three largest unique prime numbers that can be formed. If fewer than three exist, return the sum of all available primes. If no prime numbers can be formed, return 0.
Note: Each prime number should be counted only once, even if it appears in multiple substrings. Additionally, when converting a substring to an integer, any leading zeros are ignored.
Example 1:
Input: s = “12234”
Output: 1469
Explanation:
- The unique prime numbers formed from the substrings of
"12234"are 2, 3, 23, 223, and 1223. - The 3 largest primes are 1223, 223, and 23. Their sum is 1469.
Example 2:
Input: s = “111”
Output: 11
Explanation:
- The unique prime number formed from the substrings of
"111"is 11. - Since there is only one prime number, the sum is 11.
Constraints:
1 <= s.length <= 10sconsists of only digits.
public class Solution { public static HashSet millerRabinCache = new HashSet(); public long SumOfLargestPrimes(string s) { long p1 = 0; long p2 = 0; long p3 = 0; for (int i = 0; i < s.Length; i++) { long n = 0; for (int j = i; j < s.Length; j++) { n = 10 * n + (long)(s[j] - '0'); if (IsPrimeMillerRabin(n)) AddToTop3Primes(n, ref p1, ref p2, ref p3); } } return p1 + p2 + p3; } public void AddToTop3Primes(long n, ref long p1, ref long p2, ref long p3) { if (n == p1 || n == p2 || n == p3) return; if (n > p1) { p3 = p2; p2 = p1; p1 = n; } else if (n > p2) { p3 = p2; p2 = n; } else if (n > p3) { p3 = n; } } public bool IsPrimeMillerRabin(long n) { if (millerRabinCache.Contains(n)) return true; //It does not work well for smaller numbers, hence this check int SMALL_NUMBER = 1000; if (n <= SMALL_NUMBER) { bool val = IsPrime(n); if (val) millerRabinCache.Add(n); return val; } int MAX_WITNESS = 100; for (long i = 2; i <= MAX_WITNESS; i++) { if (IsPrime(i) && Witness(i, n) == 1) { return false; } } millerRabinCache.Add(n); return true; } public long SqRtN(long N) { /*++ * Using Newton Raphson method we calculate the * square root (N/g + g)/2 */ long rootN = N; int count = 0; int bitLength = 1; while (rootN / 2 != 0) { rootN /= 2; bitLength++; } bitLength = (bitLength + 1) / 2; rootN = N >> bitLength; long lastRoot = 0L; do { if (lastRoot > rootN) { if (count++ > 1000) // Work around for the bug where it gets into an infinite loop { return rootN; } } lastRoot = rootN; rootN = ((N / rootN) + rootN) >> 1; } while (!((rootN ^ lastRoot).ToString() == "0")); return rootN; } public bool IsPrime(long n) { if (n <= 1) { return false; } if (n == 2) { return true; } if (n % 2 == 0) { return false; } for (int i = 3; i <= SqRtN(n) + 1; i += 2) { if (n % i == 0) { return false; } } return true; } private int Witness(long a,long n) { long t, u; long prev, curr = 0; long i; long lln = n; u = n / 2; t = 1; while (u % 2 == 0) { u /= 2; t++; } prev = (long)BigInteger.ModPow(a, u, n); for (i = 1; i <= t; i++) { curr = (long)BigInteger.ModPow(prev, 2, lln); if ((curr == 1) && (prev != 1) && (prev != lln - 1)) return 1; prev = curr; } if (curr != 1) return 1; return 0; } }
