Goldbach Conjecture, by Alibaba
This problem comes from Alibaba, via Daily Coding Problem:
My solution is O(n)-time and O(n)-space;
This problem was asked by Alibaba.
Given an even number (greater than 2), return two prime numbers whose sum will be equal to the given number.
A solution will always exist. See Goldbach’s conjecture.
Example:
Input: 4
Output: 2 + 2 = 4
If there are more than one solution possible, return the lexicographically smaller solution.
If [a, b] is one solution with a <= b, and [c, d] is another solution with c <= d, then
[a, b] < [c, d]
If a < c OR a==c AND b < d.
- Sieve it up to n in order to cache the primes/non-primes
- Use the two-pointers (left and right) to find the answer
Hence the solution for N = 98778998 would be: 79 + 98778919
Code is on GitHub, here: https://github.com/marcelodebarros/dailycodingproblem/blob/master/DailyCodingProblem12242018.cs and also down below, cheers, Marcelo.
class DailyCodingProblem12242018 { public void MinGoldbachNumbers(long n) { if (n < 2 || n % 2 == 1) { Console.WriteLine("Invalid input"); return; } //Sieve, O(n)-time, O(n)-space Console.Write("Sieving..."); bool[] composed = new bool[n + 1]; composed[0] = composed[1] = true; for (long i = 2; i < Math.Sqrt(n); i++) for (long j = 2; i * j <= n; j++) composed[i * j] = true; Console.WriteLine("Done!"); //Two-pointers, O(n)-time long left = 2; while (composed[left]) left++; long right = n - 2; while (composed[right]) right--; while (left <= right) { if (left + right == n) { Console.WriteLine("{0} + {1} = {2}", left, right, n); break; ; } else if (left + right > n) { right--; while (composed[right]) right--; } else { left++; while (composed[left]) left++; } } } }
Comments
Post a Comment