Given an array of N integers. Each element in the array occurs the same number of times except one element. The task is to find this element.
Examples:
Input : arr[] = {1, 1, 2, 2, 3}
Output : 3
Input : arr[] = {0, 1, 2, 4, 4}
Output : 4
The idea is to use a hash table freq to store the frequencies of given elements. Once we have frequencies in the hash table, we can traverse the table to find the only value which is different from the others.
Implementation:
C++
// C++ program to find the element having// different frequency than other array// elements having same frequency#include <bits/stdc++.h>using namespace std;// Function to find the element having// different frequency from other array// elements with same frequencyint findElement(int arr[], int n){ // Store frequencies of elements unordered_map<int, int> freq; for (int i = 0; i < n; i++) { // increase the value by 1 for every // time the element occurs in an array freq[arr[i]]++; } // Below code is used find the only different // value in freq. auto it = freq.begin(); int fst_fre = it->second, fst_ele = it->first; if (freq.size() <= 2) return fst_fre; it++; int sec_fre = it->second, sec_ele = it->first; it++; int trd_fre = it->second, trd_ele = it->first; if (sec_fre == fst_fre && sec_fre != trd_fre) return trd_ele; if (sec_fre == trd_fre && sec_fre != fst_fre) return fst_ele; if (fst_fre == trd_fre && sec_fre != fst_fre) return sec_ele; // We reach here when first three frequencies are same it++; for (; it != freq.end(); it++) { if (it->second != fst_fre) return it->first; } return -1;}// Driver codeint main(){ int arr[] = { 0, 1, 2, 4, 4 }; int n = sizeof(arr) / sizeof(arr[0]); cout << findElement(arr, n) << endl; return 0;} |
Java
import java.util.*;public class DifferentFrequencyElement { // Function to find the element having different frequency // from other array elements with the same frequency static int findElement(int[] arr) { // Store frequencies of elements HashMap<Integer, Integer> freq = new HashMap<>(); for (int i = 0; i < arr.length; i++) { // Increase the value by 1 for every time the element occurs in the array freq.put(arr[i], freq.getOrDefault(arr[i], 0) + 1); } // Initialize variables to store frequencies and elements int firstFreq = -1, secondFreq = -1, thirdFreq = -1; int firstElement = -1, secondElement = -1, thirdElement = -1; for (Map.Entry<Integer, Integer> entry : freq.entrySet()) { int element = entry.getKey(); int frequency = entry.getValue(); // Update the variables based on frequency if (firstFreq == -1) { firstFreq = frequency; firstElement = element; } else if (frequency == firstFreq) { // If the current frequency is the same as the first frequency, update secondFreq and secondElement secondFreq = frequency; secondElement = element; } else if (frequency == secondFreq) { // If the current frequency is the same as the second frequency, update thirdFreq and thirdElement thirdFreq = frequency; thirdElement = element; } else { // If the frequency is different from both firstFreq and secondFreq, return the element return element; } } // If the third frequency is different, return the third element if (secondFreq == firstFreq && secondFreq != thirdFreq) return thirdElement; if (secondFreq == thirdFreq && secondFreq != firstFreq) return firstElement; if (firstFreq == thirdFreq && secondFreq != firstFreq) return secondElement; // We reach here when the first three frequencies are the same for (Map.Entry<Integer, Integer> entry : freq.entrySet()) { if (entry.getValue() != firstFreq) return entry.getKey(); } return -1; } public static void main(String[] args) { int[] arr = { 0, 1, 2, 4, 4 }; int result = findElement(arr); System.out.println(result); }} |
Python3
# Python program to find the element having # different frequency than other array # elements having same frequency # Function for above implementationdef findElement(arr, n) : # Empty dictionary to hold the values freq = {} # Initialization of frequencies of each # element to 0 for i in range(0, n) : freq[arr[i]] = 0 # Count of frequencies of elements for i in range(0, n) : freq[arr[i]] = freq[arr[i]] + 1 # Storing the first value of dictionary trd_ele = freq[0] # Variable to hold the final result position = -1 # Following loop iterates through the dictionary # and checks if frequencies are different # from the frequency of the first element for i in freq : flag = freq[i] if trd_ele != flag : # Difference has been detected position = i break # Following lines of code checks if the first # element is itself the required anomaly by # comparing the frequencies of first 3 elements fst_ele = freq[1] sec_ele = freq[2] if trd_ele != fst_ele : if trd_ele != sec_ele : for i in freq : # First element is the desired result position = i break # Final result is returned return position # Driver codearr = [ 0, 1, 2, 4, 4 ]# Variable to store length of arrayn = len(arr)print (findElement(arr, n))# This code is contributed by Pratik Basu |
C#
using System;using System.Collections.Generic;class DifferentFrequencyElement{ // Function to find the element having different frequency // from other array elements with the same frequency static int FindElement(int[] arr) { // Store frequencies of elements Dictionary<int, int> freq = new Dictionary<int, int>(); foreach (int num in arr) { // Increase the value by 1 for every time the element occurs in the array if (freq.ContainsKey(num)) { freq[num]++; } else { freq[num] = 1; } } // Initialize variables to store frequencies and elements int firstFreq = -1, secondFreq = -1, thirdFreq = -1; int firstElement = -1, secondElement = -1, thirdElement = -1; foreach (KeyValuePair<int, int> entry in freq) { int element = entry.Key; int frequency = entry.Value; // Update the variables based on frequency if (firstFreq == -1) { firstFreq = frequency; firstElement = element; } else if (frequency == firstFreq) { // If the current frequency is the same as the first frequency, update secondFreq and secondElement secondFreq = frequency; secondElement = element; } else if (frequency == secondFreq) { // If the current frequency is the same as the second frequency, update thirdFreq and thirdElement thirdFreq = frequency; thirdElement = element; } else { // If the frequency is different from both firstFreq and secondFreq, return the element return element; } } // If the third frequency is different, return the third element if (secondFreq == firstFreq && secondFreq != thirdFreq) return thirdElement; if (secondFreq == thirdFreq && secondFreq != firstFreq) return firstElement; if (firstFreq == thirdFreq && secondFreq != firstFreq) return secondElement; // We reach here when the first three frequencies are the same foreach (KeyValuePair<int, int> entry in freq) { if (entry.Value != firstFreq) return entry.Key; } return -1; } static void Main() { int[] arr = { 0, 1, 2, 4, 4 }; int result = FindElement(arr); Console.WriteLine(result); }} |
Javascript
// JavaScript implementationfunction findElement(arr, n) { // Empty object to hold the values let freq = {}; // Initialization of frequencies of each // element to 0 for(let i = 0; i < n; i++) { freq[arr[i]] = 0; } // Count of frequencies of elements for(let i = 0; i < n; i++) { freq[arr[i]] = freq[arr[i]] + 1; } // Storing the first value of object let trd_ele = freq[0]; // Variable to hold the final result let position = -1; // Following loop iterates through the object // and checks if frequencies are different // from the frequency of the first element for(let i in freq) { let flag = freq[i]; if (trd_ele !== flag) { // Difference has been detected position = i; break; } } // Following lines of code checks if the first // element is itself the required anomaly by // comparing the frequencies of first 3 elements let fst_ele = freq[1]; let sec_ele = freq[2]; if (trd_ele !== fst_ele) { if (trd_ele !== sec_ele) { for(let i in freq) { // First element is the desired result position = i; break; } } } // Final result is returned return position;}// Driver codelet arr = [ 0, 1, 2, 4, 4 ];// Variable to store length of arraylet n = arr.length;console.log(findElement(arr, n));// This code is contributed by phasing17 |
Output
4
Complexity Analysis:
- Time Complexity: O(n)
- Auxiliary Space: O(n)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
