Find the only non-repeating element in a given array

0 0 7 minutes read

Given an array A[] consisting of N (1 ? N ? 10⁵) positive integers, the task is to find the only array element with a single occurrence.

Note: It is guaranteed that only one such element exists in the array.

Examples:

Input: A[] = {1, 1, 2, 3, 3}
Output: 2
Explanation:
Distinct 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 array elements.
Traverse the Map and find the element with frequency 1 and print that element.

Below is the implementation of the above approach:

C++

// C++ implementation of the
// above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function call to find
// element in A[] with frequency = 1
void CalcUnique(int A[], int N)
{
    // Stores frequency of
    // array elements
    unordered_map<int, int> freq;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
        // Update frequency of A[i]
        freq[A[i]]++;
    }
 
    // Traverse the Map
    for (int i = 0; i < N; i++) {
 
        // If non-repeating element
        // is found
        if (freq[A[i]] == 1) {
 
            cout << A[i];
            return;
        }
    }
}
 
// Driver Code
int main()
{
    int A[] = { 1, 1, 2, 3, 3 };
    int N = sizeof(A) / sizeof(A[0]);
 
    CalcUnique(A, N);
 
    return 0;
}

Java

// Java implementation of the
// above approach
import java.util.*;
class GFG
{
 
  // Function call to find
  // element in A[] with frequency = 1
  static void CalcUnique(int A[], int N)
  {
    // Stores frequency of
    // array elements
    HashMap<Integer,Integer> freq = new HashMap<Integer,Integer>();
 
    // Traverse the array
    for (int i = 0; i < N; i++)
    {
 
      // Update frequency of A[i]
      if(freq.containsKey(A[i]))
      {
        freq.put(A[i], freq.get(A[i]) + 1);
      }
      else
      {
        freq.put(A[i], 1);
      }
    }
 
    // Traverse the Map
    for (int i = 0; i < N; i++)
    {
 
      // If non-repeating element
      // is found
      if (freq.containsKey(A[i])&&freq.get(A[i]) == 1)
      {
        System.out.print(A[i]);
        return;
      }
    }
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int A[] = { 1, 1, 2, 3, 3 };
    int N = A.length;
    CalcUnique(A, N);
  }
}
 
// This code is contributed by 29AjayKumar

Python3

# Python 3 implementation of the
# above approach
from collections import defaultdict
 
# Function call to find
# element in A[] with frequency = 1
def CalcUnique(A, N):
 
    # Stores frequency of
    # 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 Code
if __name__ == "__main__":
    A = [1, 1, 2, 3, 3]
    N = len(A)
    CalcUnique(A, N)
 
    # This code is contributed by chitranayal.

C#

// C# implementation of the
// above approach
using System;
using System.Collections.Generic;
 
public class GFG
{
 
  // Function call to find
  // element in []A with frequency = 1
  static void CalcUnique(int []A, int N)
  {
     
    // Stores frequency of
    // array elements
    Dictionary<int,int> freq = new Dictionary<int,int>();
 
    // Traverse the array
    for (int i = 0; i < N; i++)
    {
 
      // Update frequency of A[i]
      if(freq.ContainsKey(A[i]))
      {
        freq[A[i]] = freq[A[i]] + 1;
      }
      else
      {
        freq.Add(A[i], 1);
      }
    }
 
    // Traverse the Map
    for (int i = 0; i < N; i++)
    {
 
      // If non-repeating element
      // is found
      if (freq.ContainsKey(A[i]) && freq[A[i]] == 1)
      {
        Console.Write(A[i]);
        return;
      }
    }
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    int []A = { 1, 1, 2, 3, 3 };
    int N = A.Length;
    CalcUnique(A, N);
  }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// JavaScript implementation of the
// above approach
 
// Function call to find
// element in A[] with frequency = 1
function CalcUnique(A, N)
{
    // Stores frequency of
    // array elements
    var freq = new Map();
 
    // Traverse the array
    for (var i = 0; i < N; i++) {
 
        // Update frequency of A[i]
        if(freq.has(A[i]))
        {
            freq.set(A[i], freq.get(A[i])+1);
        }
        else
        {
            freq.set(A[i],1);
        }
    }
 
    // Traverse the Map
    for (var i = 0; i < N; i++) {
 
        // If non-repeating element
        // is found
        if (freq.get(A[i]) == 1) {
 
            document.write( A[i]);
            return;
        }
    }
}
 
// Driver Code
var A = [1, 1, 2, 3, 3 ];
var N = A.length;
CalcUnique(A, N);
 
</script>

Output:

Time Complexity : O(N)
Auxiliary Space : O(N)

Another Approach: Using Built-in Functions:

Calculate the frequencies using Built-In function.
Traverse the array and find the element with frequency 1 and print it.

Below is the implementation:

C++

#include <iostream>
#include <unordered_map>
using namespace std;
 
// Function call to find element in A[] with frequency = 1
void CalcUnique(int A[], int N)
{
 
  // Calculate frequency of all array elements
  unordered_map<int, int> freq;
 
  // Traverse the Array
  for (int i = 0; i < N; i++) 
  {
 
    // Update frequency of each array element in the map
    int count = 1;
    if (freq.count(A[i])) {
      count = freq[A[i]];
      count++;
    }
    freq[A[i]] = count;
  }
 
  // Traverse the Array
  for (int i = 0; i < N; i++) 
  {
 
    // If non-repeating element is found
    if (freq[A[i]] == 1) {
      cout << A[i] << endl;
      return;
    }
  }
}
 
// Driver Code
int main()
{
  int A[] = { 1, 1, 2, 3, 3 };
  int N = sizeof(A) / sizeof(A[0]);
  CalcUnique(A, N);
  return 0;
}

Java

//Java code:
import java.util.Map;
import java.util.HashMap;
class Main{
// Function call to find
// element in A[] with frequency = 1
public static void CalcUnique(int A[], int N)
{
    // Calculate frequency of 
    // all array elements
    Map<Integer, Integer> freq = new HashMap<Integer, Integer>();
     
    // Traverse the Array
    for (int i=0; i<N; i++)
    {
        // Update frequency of each
        // array element in the map
        int count = 1;
        if(freq.containsKey(A[i]))
        {
            count = freq.get(A[i]);
            count++;
        }
        freq.put(A[i], count);
    }
     
    // Traverse the Array
    for (int i=0; i<N; i++)
    {
        // If non-repeating element
        // is found
        if (freq.get(A[i]) == 1)
        {
            System.out.println(A[i]);
            return;
        }
    }
}
  
// Driver Code
public static void main(String args[])
{
    int A[] = {1, 1, 2, 3, 3};
    int N = A.length;
    CalcUnique(A, N);
}}

Python3

# Python 3 implementation of the
# above approach
from collections import Counter
 
# Function call to find
# element in A[] with frequency = 1
def CalcUnique(A, N):
 
    # Calculate frequency of 
    # all 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 Code
if __name__ == "__main__":
    A = [1, 1, 2, 3, 3]
    N = len(A)
    CalcUnique(A, N)
 
# This code is contributed by vikkycirus

C#

using System;
using System.Collections.Generic;
 
public class MainClass {
 
  // Function call to find element in A[] with frequency =
  // 1
  static void CalcUnique(int[] A, int N)
  {
 
    // Calculate frequency of all array elements
    Dictionary<int, int> freq
      = new Dictionary<int, int>();
 
    // Traverse the Array
    for (int i = 0; i < N; i++) {
 
      // Update frequency of each array element in the
      // dictionary
      if (freq.ContainsKey(A[i])) {
        freq[A[i]]++;
      }
      else {
        freq[A[i]] = 1;
      }
    }
 
    // Traverse the Array
    for (int i = 0; i < N; i++) {
 
      // If non-repeating element is found
      if (freq[A[i]] == 1) {
        Console.WriteLine(A[i]);
        return;
      }
    }
  }
 
  // Driver Code
  public static void Main()
  {
    int[] A = { 1, 1, 2, 3, 3 };
    int N = A.Length;
    CalcUnique(A, N);
  }
}

Javascript

<script>
// Function call to find
// element in A[] with frequency = 1
function CalcUnique(A) {
  // Calculate frequency of 
  // all array elements
  let freq = A.reduce((acc, curr) => {
    if (acc[curr]) {
      acc[curr]++;
    } else {
      acc[curr] = 1;
    }
    return acc;
  }, {});
 
  // Traverse the Array
  for (let i = 0; i < A.length; i++) {
    // If non-repeating element
    // is found
    if (freq[A[i]] === 1) {
      console.log(A[i]);
      return;
    }
  }
}
 
// Driver Code
const A = [1, 1, 2, 3, 3];
CalcUnique(A);
 
</script>

Output

Time Complexity: O(N)
Auxiliary Space: O(N)

Another Approach: Using Sorting

The idea is to sort the array and find which element occurs only 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 the array is already sorted that’s why repeating element will be consecutive
So in that whole array, we will find which element occurred only once. That is our required answer

Code-

C++

#include <bits/stdc++.h>
using namespace std;
 
// Function call to find single non-repeating element
void CalcUnique(int arr[], int N)
{
 
 //Sort the Array
 sort(arr,arr+N);
 
int temp=INT_MIN;
int count=0;
 
  // Traverse the Array
  for(int i=0;i<N;i++){
      if(arr[i]==temp){count++;}
      else{
          if(count==1){
              cout<<temp<<endl;
              return;
          }
          temp=arr[i];
          count=1;
      }
  }
   
  //If yet not returned from the function then last element is the only non-repeating element
  cout<<arr[N-1]<<endl;
   
}
 
// Driver Code
int main()
{
  int arr[] = {1, 1, 2, 3, 3};
  int N = sizeof(arr) / sizeof(arr[0]);
  CalcUnique(arr, N);
  return 0;
}

Java

import java.util.*;
 
public class Main {
      // Function call to find single non-repeating element
    public static void CalcUnique(int[] arr, int N) {
 
        // Sort the Array
        Arrays.sort(arr);
 
        int temp=Integer.MIN_VALUE;
        int count=0;
 
        // Traverse the Array
        for(int i=0;i<N;i++){
            if(arr[i]==temp){
                count++;
            } else {
                if(count==1){
                    System.out.println(temp);
                    return;
                }
                temp=arr[i];
                count=1;
            }
        }
 
        // If yet not returned from the function then last element is the only non-repeating element
        System.out.println(arr[N-1]);
        }
 
    // Driver Code
    public static void main(String[] args) {
        int[] arr = {1, 1, 2, 3, 3};
        int N = arr.length;
        CalcUnique(arr, N);
    }
}

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 only non-repeating element
    print(arr[N-1])
 
# Driver Code
if __name__ == "__main__":
    arr = [1, 1, 2, 3, 3]
    N = len(arr)
    calc_unique(arr, N)

Output

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

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!