Given an array of size N, print the index of the distinct element from the array, provided the array has only one distinct element and rest other elements are same.
Examples:
Input: Arr[]={10,10,10,10,20}
Output: Distinct Element found at index : 4
Input: Arr[]={7,7,7,0,7,7,7,7}
Output: Distinct Element found at index : 3
Approach:
Linearly traverse through the array and find the element which is not equal to its neighbouring element and return its index.
Below is the C++ implementation of the above approach:
#include <iostream>
using namespace std;
int distnctInd(int arr[],int n){
int itr = arr[0];
for (int i=1; i<n; i++){
if (itr!=arr[i] && arr[i+1]!=arr[i]){
return i;
}else if (itr!=arr[i] && arr[i+1]==arr[i]){
return i-1;
}else if (itr==arr[i] && arr[i+1]!=arr[i]){
return i+1;
}else{
itr=arr[i];
}
}
}
int main() {
int arr[]={9,9,9,9,6,9,9};
int arrsize=sizeof(arr)/sizeof(arr[0]);
cout<< "Distinct Element found at index : " << distnctInd(arr,arrsize) <<endl;
return 0;
}
Output:
Distinct Element found at index : 4
Time Complexity: O(N)
Space Complexity: O(1)
