Input is a sequence X of n real numbers, not necessarily in sorted order. It is
ID: 3763129 • Letter: I
Question
Input is a sequence X of n real numbers, not necessarily in sorted order. It is known that n = 4k + 3 for some integer k and that X has k elements such that each of them appears 4 times and another element that appears 3 times. For example X would be 7.2, 6.15, 6.15, 8.4, 8.4, 7.2, 7.2, 6.15, 8.4. Here k = 2. The elements 7.2 and 8.4 appear 4 times each and the element 6.15 appears thrice. The problem is to identify the element that occurs three times. Present an O(n) time algorithm for this problem.Explanation / Answer
we can solve this problem in o(n).
the trick here is to use xor operation. Since other elements occur in multiple of 4 times they all will cancel each other as 0^0 =0 and 1^1=0.
So if we just take the array and do xor of all the elements we will find the element which is coming 3 times in the array as it will be the value which will be left out after xor operation.
working c++ code
#include <iostream>
using namespace std;
int main() {
// your code goes here
int arr[]={4,3,4,3,4,3,4};
int bit=0;
for(int i=0;i<7;i++)
bit=bit^arr[i];
cout<<bit;
return 0;
}
output:
3