Find the only element that appears b times

0 0 8 minutes read

Given an array where every element occurs ‘a’ times, except one element which occurs b (a>b) times. Find the element that occurs b times.

Examples:

Input : arr[]  = [1, 1, 2, 2, 2, 3, 3, 3]
         a = 3, b = 2
Output : 1

Add each number once and multiply the sum by a, we will get a times the sum of each element of the array. Store it as a_sum. Subtract the sum of the whole array from the a_sum and divide the result by (a-b). The number we get is the required number (which appears b times in the array).

Steps to solve this problem:

1. declare an unordered map s.

2. initialize two variable a_sum=0 and sum=0.

3. iterate through i=0 to n:

*check if arr[i] is not present in s than insert arr[i] in s and update a_sum to a_sum+arr[i].

*update sum to sum + arr[i].

4. update a_sum to a*a_sum.

5. return ((a_sum-sum)/(a-b)).

Implementation:

C++

// CPP program to find the only element that 
// appears b times
#include <bits/stdc++.h>
using namespace std;
 
int appearsbTimes(int arr[], int n, int a, int b)
{
    unordered_set<int> s;
 
    int a_sum = 0, sum = 0;
 
    for (int i = 0; i < n; i++) {
        if (s.find(arr[i]) == s.end()) {
            s.insert(arr[i]);
            a_sum += arr[i];
        }
 
        sum += arr[i];
    }
 
    a_sum = a * a_sum;
 
    return ((a_sum - sum) / (a - b));
}
 
int main()
{
    int arr[] = { 1, 1, 2, 2, 2, 3, 3, 3 };
    int a = 3, b = 2;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << appearsbTimes(arr, n, a, b);
    return 0;
}

Java

// Java program to find the only element that 
// appears b times
import java.util.*;
 
class GFG 
{
static int appearsbTimes(int arr[], int n, 
                         int a, int b)
{
    HashSet<Integer> s = new HashSet<Integer>();
 
    int a_sum = 0, sum = 0;
 
    for (int i = 0; i < n; i++)
    {
        if (!s.contains(arr[i]))
        {
            s.add(arr[i]);
            a_sum += arr[i];
        }
 
        sum += arr[i];
    }
    a_sum = a * a_sum;
 
    return ((a_sum - sum) / (a - b));
}
 
// Driver Code
public static void main(String[] args) 
{
    int arr[] = { 1, 1, 2, 2, 2, 3, 3, 3 };
    int a = 3, b = 2;
    int n = arr.length;
    System.out.println(appearsbTimes(arr, n, a, b));
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program to find the only 
# element that appears b times
def appearsbTimes(arr, n, a, b):
 
    s = dict()
 
    a_Sum = 0
    Sum = 0
 
    for i in range(n):
        if (arr[i] not in s.keys()):
            s[arr[i]] = 1
            a_Sum += arr[i]
 
        Sum += arr[i]
         
    a_Sum = a * a_Sum
 
    return ((a_Sum - Sum) // (a - b))
 
# Driver code
arr = [1, 1, 2, 2, 2, 3, 3, 3]
a, b = 3, 2
n = len(arr)
print(appearsbTimes(arr, n, a, b))
 
# This code is contributed by mohit kumar

C#

// C# program to find the only element that 
// appears b times
using System;
using System.Collections.Generic;
 
class GFG 
{
     
static int appearsbTimes(int []arr, int n, 
                        int a, int b)
{
    HashSet<int> s = new HashSet<int>();
 
    int a_sum = 0, sum = 0;
 
    for (int i = 0; i < n; i++)
    {
        if (!s.Contains(arr[i]))
        {
            s.Add(arr[i]);
            a_sum += arr[i];
        }
 
        sum += arr[i];
    }
    a_sum = a * a_sum;
 
    return ((a_sum - sum) / (a - b));
}
 
// Driver Code
public static void Main(String[] args) 
{
    int []arr = { 1, 1, 2, 2, 2, 3, 3, 3 };
    int a = 3, b = 2;
    int n = arr.Length;
    Console.WriteLine(appearsbTimes(arr, n, a, b));
}
}
 
// This code is contributed by Princi Singh

Javascript

<script>
 
// Javascript program to find the only element that 
// appears b times
 
function appearsbTimes(arr, n, a, b)
{
    var s = new Set();
 
    var a_sum = 0, sum = 0;
 
    for (var i = 0; i < n; i++) {
        if (!s.has(arr[i])) {
            s.add(arr[i]);
            a_sum += arr[i];
        }
 
        sum += arr[i];
    }
 
    a_sum = a * a_sum;
 
    return ((a_sum - sum) / (a - b));
}
 
var arr = [1, 1, 2, 2, 2, 3, 3, 3];
var a = 3, b = 2;
var n = arr.length;
document.write( appearsbTimes(arr, n, a, b));
</script>

Output

Complexity Analysis:

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

Please refer to the article below for more approaches.
Find the only element that appears k times.

Another Approach:-

We can use sorting to solve this problem

Sort the given array

iterate over array and count the frequency of elements

If found the frequency of a element b then return it.

Implementation:-

C++

// CPP program to find the only element that 
// appears b times
#include <bits/stdc++.h>
using namespace std;
 
int appearsbTimes(int arr[], int n, int a, int b)
{
    //sorting the array
      sort(arr,arr+n);
      //taking the first element
      int temp=arr[0];
      //taking the initial frequency of first element as 1
      int count=1;
      for(int i=1;i<n;i++)
    {
          //increasing frequency
          if(arr[i]==temp)count++;
          //got another element
          else
        {
              //checking the frequency of the previous element
              //if it was b then return it
              if(count==b)return arr[i-1];
              count=1;
              temp=arr[i];
        }
    }
}
 
int main()
{
    int arr[] = { 1, 1, 2, 2, 2, 3, 3, 3 };
    int a = 3, b = 3;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << appearsbTimes(arr, n, a, b);
    return 0;
}

Java

import java.util.Arrays;
 
public class Main {
  public static int appearsbTimes(int[] arr, int n, int a, int b) 
  {
 
    // sorting the array
    Arrays.sort(arr);
 
    // taking the first element
    int temp = arr[0];
 
    // taking the initial frequency of first element as 1
    int count = 1;
    for (int i = 1; i < n; i++)
    {
 
      // increasing frequency
      if (arr[i] == temp)
        count++;
 
      // got another element
      else
      {
         
        // checking the frequency of the previous element
        // if it was b then return it
        if (count == b)
          return arr[i - 1];
        count = 1;
        temp = arr[i];
      }
    }
    return -1;
  }
 
  public static void main(String[] args) {
    int[] arr = {1, 1, 2, 2, 2, 3, 3, 3};
    int a = 3, b = 2;
    int n = arr.length;
    System.out.println(appearsbTimes(arr, n, a, b));
  }
}

Python3

# CPP program to find the only element that
# appears b times
 
def appears_b_times(arr, n, a, b):
    #sorting the array
    arr.sort()
    #taking the first element
    temp = arr[0]
    #taking the initial frequency of first element as 1
    count = 1
    for i in range(1, n):
        #increasing frequency
        if arr[i] == temp:
            count += 1
        #got another element
        else:
            #checking the frequency of the previous element
            #if it was b then return it
            if count == b:
                return arr[i-1]
            count = 1
            temp = arr[i]
 
#driver code
arr = [1, 1, 2, 2, 2, 3, 3, 3]
a = 3
b = 2
n = len(arr)
print(appears_b_times(arr, n, a, b))

C#

// C# program to find the only element that 
// appears b times
using System;
public class GFG
{
  public static int appearsbTimes(int[] arr, int n, int a, int b)
  {
    // sorting the array
    Array.Sort(arr);
 
    // taking the first element
    int temp = arr[0];
 
    // taking the initial frequency of first element as 1
    int count = 1;
    for (int i = 1;i < n;i++)
    {
      // increasing frequency
      if (arr[i] == temp)
      {
        count++;
      }
      // got another element
      else
      {
        // checking the frequency of the previous element
        // if it was b then return it
        if (count == b)
        {
          return arr[i - 1];
        }
        count = 1;
        temp = arr[i];
      }
    }
    return -1;
  }
 
  internal static void Main()
  {
    int[] arr = {1, 1, 2, 2, 2, 3, 3, 3};
    int a = 3;
    int b = 2;
 
    int n = arr.Length;
    Console.Write(appearsbTimes(arr, n, a, b));
  }
}
 
// This code is contributed by bhardwajji

Javascript

function appearsbTimes(arr, n, a, b) {
  // Sorting the array
  arr.sort((x, y) => x - y);
  // Taking the first element
  let temp = arr[0];
  // Taking the initial frequency of first element as 1
  let count = 1;
  for (let i = 1; i < n; i++) {
    // Increasing frequency
    if (arr[i] === temp) {
      count++;
    }
    // Got another element
    else {
      // Checking the frequency of the previous element
      // If it was b then return it
      if (count === b) {
        return arr[i - 1];
      }
      count = 1;
      temp = arr[i];
    }
  }
}
 
const arr = [1, 1, 2, 2, 2, 3, 3, 3];
const a = 3, b = 3;
const n = arr.length;
console.log(appearsbTimes(arr, n, a, b));

Output

Time Complexity:- O(NLogN)
Auxiliary Space:- O(1)

Another Approach:-

We can use hashmap to store frequency

After this just traverse the hashmap and find which element has frequency b and return that element.

Implementation:-

C++

#include <bits/stdc++.h>
using namespace std;
 
int appearsbTimes(int arr[], int n, int a, int b)
{
      //hashmap to store frequency
      unordered_map<int,int> mm;
       
      //iterating to store frequency
      for(int i=0;i<n;i++)mm[arr[i]]++;
   
      //iterating over array to get element with frequrecy b
      for(auto x:mm)
    {
          //checking for frequency b
          if(x.second==b)return x.first;
    }
}
 
int main()
{
    int arr[] = { 1, 1, 2, 2, 2, 3, 3, 3 };
    int a = 3, b = 2;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << appearsbTimes(arr, n, a, b);
    return 0;
}
//This code is contributed by shubhamrajput6156

Java

// Java implementation of above approach
import java.util.*;
 
public class GFG {
  static int appearsbTimes(int arr[], int n, int a, int b) {
 
    // hashmap to store frequency
    Map<Integer,Integer> mm = new HashMap<>();
 
    // iterating to store frequency
    for(int i = 0; i < n; i++) mm.put(arr[i], mm.getOrDefault(arr[i], 0) + 1);
 
    // iterating over map to get element with frequency b
    for(Map.Entry<Integer,Integer> entry : mm.entrySet()) {
 
      // checking for frequency b
      if(entry.getValue() == b) return entry.getKey();
    }
    return -1; // if not found
  }
 
  // Driver Code
  public static void main(String[] args) {
    int arr[] = { 1, 1, 2, 2, 2, 3, 3, 3 };
    int a = 3, b = 2;
    int n = arr.length;
 
    // Function Call
    System.out.println(appearsbTimes(arr, n, a, b));
  }
}
 
// this code is contributed by bhardwajji

Python3

def appearsbTimes(arr, n, a, b):
    # dictionary to store frequency
    mm = {}
 
    # iterating to store frequency
    for i in range(n):
        mm[arr[i]] = mm.get(arr[i], 0) + 1
 
    # iterating over dictionary to get element with frequency b
    for x in mm.items():
        # checking for frequency b
        if x[1] == b:
            return x[0]
 
 
arr = [1, 1, 2, 2, 2, 3, 3, 3]
a, b = 3, 2
n = len(arr)
print(appearsbTimes(arr, n, a, b))

C#

using System;
using System.Collections.Generic;
using System.Linq;
 
public class GFG{
    static int appearsbTimes(int[] arr, int n, int a, int b)
    {
        //dictionary to store frequency
        Dictionary<int, int> mm = new Dictionary<int, int>();
         
        //iterating to store frequency
        for (int i = 0; i < n; i++)
        {
            if (mm.ContainsKey(arr[i]))
            {
                mm[arr[i]]++;
            }
            else
            {
                mm.Add(arr[i], 1);
            }
        }
         
        //iterating over dictionary to get element with frequency b
        foreach (KeyValuePair<int, int> x in mm)
        {
            //checking for frequency b
            if (x.Value == b)
            {
                return x.Key;
            }
        }
         
        return -1; //element not found
    }
     
    static void Main(string[] args)
    {
        int[] arr = { 1, 1, 2, 2, 2, 3, 3, 3 };
        int a = 3, b = 2;
        int n = arr.Length;
        Console.WriteLine(appearsbTimes(arr, n, a, b));
    }
 
}

Javascript

function appearsbTimes(arr, n, a, b)
{
 
    // hashmap to store frequency
    const mm = new Map();
     
    // iterating to store frequency
    for (let i = 0; i < n; i++) {
        mm.set(arr[i], (mm.get(arr[i]) || 0) + 1);
    }
   
    // iterating over array to get element with frequency b
    for (const [key, value] of mm)
    {
     
        // checking for frequency b
        if (value === b) {
            return key;
        }
    }
}
 
const arr = [1, 1, 2, 2, 2, 3, 3, 3];
const a = 3;
const b = 2;
const n = arr.length;
console.log(appearsbTimes(arr, n, a, b));

Output

Time Complexity:- O(N)
Space Complexity:- 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 zambiatek!