Sample Question 2

gistfile1.txt

An integer X and a non-empty zero-indexed array A consisting of N integers are given. We are interested in which elements of A are equal to X and which are different from X. The goal is to split array A into two parts, such that the number of elements equal to X in the first part is the same as the number of elements different from X in the other part. More formally, we are looking for a number K such that:

0 <= K  <= N
the number of elements equal to X in A[0..K−1] is the same as the number of elements different from X in A[K..N−1]. (For K = 0, A[0..K−1] does not contain any elements. For K = N, A[K..N−1] does not contain any elements.)

  A[0] = 5
  A[1] = 5
  A[2] = 1
  A[3] = 7
  A[4] = 2
  A[5] = 3
  A[6] = 5

K equals 4, because:
two of the elements of A[0..3] are equal to X, namely A[0] = A[1] = X, and<
two of the elements of A[4..6] are different from X, namely A[4] and A[5].