Find just non-repeating element in a given array
Given an array A [] consisting of N (1 ? N ? 105) positive integers, the task is to find the just an array element with a single occurrence.Â
Note: It is guaranteed that just one such element exists in the array.
Examples:
Input: A[] = {1, 1, 2, 3, 3}
Output: 2
Explanation:Â
Distinct an array elements are {1, 2, 3}.Â
Frequency of these elements are {2, 1, 2} respectively.Input : A[] = {1, 1, 1, 2, 2, 3, 5, 3, 4, 4}
Output : 5
Approach: Follow the steps below to solve the problem
- Traverse the array
- Use an Unordered Map to store the frequency of an array elements.
- Traverse the Map and find the element with frequency 1 and print that element.
Python3
# Python 3 implementation of the# above approachfrom collections import defaultdict# Function call to find# element in A[] with frequency = 1def CalcUnique(A, N):    # Stores frequency of    # an array elements    freq = defaultdict(int)    # Traverse the array    for i in range(N):        # Update frequency of A[i]        freq[A[i]] += 1    # Traverse the Map    for i in range(N):        # If non-repeating element        # is found        if (freq[A[i]] == 1):            print(A[i])            return# Driver Codeif __name__ == "__main__":    A = [1, 1, 2, 3, 3]    N = len(A)    CalcUnique(A, N)    # This code is contributed by chitranayal. |
Output
2
Time Complexity : O(N)
Auxiliary Space : O(N)
Another Approach: Using Built-in Functions:
- Calculate the frequencies using Built-In function.
- Traverse the an array and find the element with frequency 1 and print it.
Below is the implementation:
Python3
# Python 3 implementation of the# above approachfrom collections import Counter# Function call to find# element in A[] with frequency = 1def CalcUnique(A, N):    # Calculate frequency of     # all an array elements    freq = Counter(A)        # Traverse the Array    for i in A:        # If non-repeating element        # is found        if (freq[i] == 1):            print(i)            return# Driver Codeif __name__ == "__main__":    A = [1, 1, 2, 3, 3]    N = len(A)    CalcUnique(A, N)# This code is contributed by vikkycirus |
Output
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Another Approach: Using Sorting
The idea is to sort an array and find which element occurs just once by traversing the array.
Steps to implement this Approach-
- Sort the given array
- Then traverse from starting to the end of the array
- Since an array is already sorted that’s why repeating element will be consecutive
- So in that whole array, we will find which element occurred just once. That is our required answer
Code-
Python3
def calc_unique(arr, N):    # Sort the array    arr.sort()    temp = None    count = 0    # Traverse the array    for i in range(N):        if arr[i] == temp:            count += 1        else:            if count == 1:                print(temp)                return            temp = arr[i]            count = 1    # If yet not returned from the function,     # then the last element is the just non-repeating element    print(arr[N-1])# Driver Codeif __name__ == "__main__":    arr = [1, 1, 2, 3, 3]    N = len(arr)    calc_unique(arr, N) |
Output
2
Time Complexity: O(NlogN)+O(N)=O(NlogN), O(NlogN) in sorting and O(N) in traversing the array
Auxiliary Space: O(1), because no extra space has been taken