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 timesimport 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 Codepublic 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 timesdef 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 codearr = [1, 1, 2, 2, 2, 3, 3, 3]a, b = 3, 2n = 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 timesusing 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 Codepublic 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 timesfunction 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
1
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 timesdef 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 codearr = [1, 1, 2, 2, 2, 3, 3, 3]a = 3b = 2n = len(arr)print(appears_b_times(arr, n, a, b)) |
C#
// C# program to find the only element that // appears b timesusing 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
2
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 approachimport 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, 2n = 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
1
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
