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 an index K such that:
- 0 ≤ K < N and
- 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.)
For example, given integer X = 5 and array A such that:
A = [5, 5, 1, 7, 2, 3, 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].
Write a function:
int solution(int X, int A[], int N);
that, given an integer X and a non-empty zero-indexed array A consisting of N integers, returns the value of index K satisfying the above conditions. It can be shown such index K always exists and it is unique.
For example, given integer X and array A as above, the function should return 4, as explained above.
Assume that:
- N is an integer within the range [1..100,000];
- X is an integer within the range [0..100,000];
- Each element of array A is an integer within the range [0..100,000].
Complexity:
- Expected worst-case time complexity is O(N);
- Expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.
function solution(X, A) {
N = A.length;
let sum = 0, chunk = 0;
for (let i=0; i<N; i++) {
if (A[i]==X) {
sum++;
seg++;
} else {
seg = 0;
}
}
return (sum > chunk) && !!sum ? (N-sum) : -1;
}