Goldbach Conjecture, by Alibaba

This problem comes from Alibaba, via Daily Coding Problem:

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.

My solution is O(n)-time and O(n)-space;

• 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/BorisVasilenko/dailycodingproblem/blob/master/DailyCodingProblem12242018.cs and also down below, cheers, Boris.

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++;
   }
  }
 }
}