We are given an array consisting of N numbers, and a number X. We need to find an index K in this array that divides the array into two parts(0 to K-1, and K-1 to N-1) as such: Number of elements equal to X in the first part = Number of elements not equal to X in the second part. Example: A = (5, 5, 1, 2, 3, 4, 5), X = 5 Answer: K= 4 (5, 5, 1, 2) contains two X's. (3, 4, 5) contains two non X's. Such K always exists according to the problem description. The solution needs to have an O(N) complexity. O(N^2) solution is too easy, yet I could not find the O(N) one. Thanks for your help!
