Find the just distinct element in an array
Input: arr[] = {10, 10, 10, 20, 10, 10}
Output: 3
arr[3] is the just distinct element.Input: arr[] = {30, 10, 30, 30, 30}
Output: 1
arr[1] is the just distinct element.
A simple solution is to traverse the array. For every element, check if it is distinct from others or not. The time complexity of this solution would be O(n*n)
A better solution is to use hashing. We count frequencies of all elements. The hash table will have two elements. We print the element with value (or frequency) equal to 1. This solution works in O(n) time but requires O(n) extra space.
An efficient solution is to first check the first three elements. There can be two cases,
- Two elements are same, i.e., one is distinct according to given conditions in the question. In this case, the distinct element is among the first three, so we return the distinct element.
- All three elements are same. In this case, the distinct element lies in the remaining array. So, we traverse an array from the fourth element and simply check if the value of the current element is distinct from previous or not.
Below is the implementation of the above idea.
Python3
# Python3 program to find the just # distinct element in an array. # Function to find minimum range # increments to sort an array def findTheOnlyDifferent(arr, n):     # Array size must be at least two.     if n == 1:         return -1    # If there are two elements,     # then we can return any one     # element when distinct     if n == 2:         return 0    # Check if the distinct element     # is among first three     if arr[0] == arr[1] and arr[0] != arr[2]:         return 2    if arr[0] == arr[2] and arr[0] != arr[1]:         return 1    if arr[1] == arr[2] and arr[0] != arr[1]:         return 0    # If we reach here, then first     # three elements must be same     # (assuming that just one element     # is different.     for i in range(3, n):         if arr[i] != arr[i - 1]:             return i     return -1# Driver Codeif __name__ == "__main__":        arr = [10, 20, 20, 20, 20]     n = len(arr)   print(findTheOnlyDifferent(arr, n)) |
0
SECOND APPROACH: Using STL
Another approach to this problem is by using vector functions/method. similar as we will simply copy all the element in another an array and then we will simply compare the first element of new sorted an array with previous one and the index which is not same will be our answer.
Below is the implementation of the above approach:
Python3
# Python3 program to find the just different# Function to solve the problemdef solve():# Initialize an arrayarr = [10, 20, 20, 20, 20]n = len(arr)# Create a copy of the an array and sort itarr2 = arr.copy()arr2.sort()# Loop through the original an array and print the indices# of elements that are not equal to the second smallest elementfor i in range(n):if arr[i] != arr2[1]:print(i)# Call the solve functionsolve() |
0