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) |
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) |
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