Sum of two (Editorial)

Let $v$ be the input array of numbers. Initialize pointers i = 0 to the beginning of the array and j = n - 1 to the end of the array. The array is already sorted according to the problem conditions.

While pointers $i$ and $j$ do not meet, perform the following actions:

• If v_i + v_j = x, then the desired pair of elements is found. Print it and terminate the program.

• If v_i + v_j < x, then move pointer $i$ one position to the right. In this case, the sum v_i + v_j will increase;

• If v_i + v_j > x, then move pointer $j$ one position to the left. In this case, the v_i + v_j will decrease;

Example

Let’s consider the first test. Initialize the pointers. Simulate the algorithm’s operation. The value of x = 13, we are looking for two numbers with a sum of $13$.

Algorithm realization

Read the input data.

scanf("%d %d", &n, &x);
v.resize(n);
for (i = 0; i < n; i++)
  scanf("%d", &v[i]);

Initialize the pointers.

int i = 0, j = v.size() - 1;

Move pointer $i$ forward and pointer $j$ backward.

while (i < j)
{

If v_i + v_j = x, then the desired pair of elements is found. Print it and terminate the program.

  if (v[i] + v[j] == x)
  {
    printf("YES\n");
    return 0;
  }

If v_i + v_j < x, then move pointer $i$ one position to the right;

If v_i + v_j > x, then move pointer $j$ one position to the left;

  if (v[i] + v[j] < x) i++; else j--;
}

If the desired pair is not found, print "NO".

printf("NO\n");

Java realization

import java.util.*;
 
public class Main
{
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    int x = con.nextInt();
    int v[] = new int[n];
    for(int i = 0; i < n; i++)
      v[i] = con.nextInt();

    int i = 0, j = n - 1;
    while (i < j)
    {
      if (v[i] + v[j] == x)
      {
        System.out.println("YES");
        return;
      }
      if (v[i] + v[j] < x) i++; else j--;
    }
    System.out.println("NO");
    con.close();
  }
}

Python realization

Read the input data.

n, x = map(int,input().split())
lst = list(map(int,input().split()))

Initialize the pointers.

i = 0
j = n – 1

Move pointer $i$ forward and pointer $j$ backward.

while (i < j):

If v_i + v_j = x, then the desired pair of elements is found. Print it and terminate the program.

  if (lst[i] + lst[j] == x):
    print("YES")
    exit()

If v_i + v_j < x, then move pointer $i$ one position to the right;

If v_i + v_j > x, then move pointer $j$ one position to the left;

  if (lst[i] + lst[j] < x):
    i += 1
  else:
    j -= 1

If the desired pair is not found, print "NO".

print("NO")