PUBLISH - Editorial

editorial
1

PROBLEM LINK:

Contest

Author: Sumukh Bhardwaj
Tester: Rahul Sharma
Editorialist: Sumukh Bhardwaj

DIFFICULTY:

EASY

PREREQUISITES:

Basic Programming

PROBLEM:

Given an array of integers nums, return the largest integer that only occurs once.
If no integer occurs once, return -1.

QUICK EXPLANATION:

Count the frequency of all the elements and return the one having the frequency as 1 and having the largest value.

EXPLANATION:

we can use a hash map to store the count of each number. Since hash maps are unordered we need to traverse it to find out if the count of the current element is 1. If it is, it is a candidate for our answer. We take the maximum of these candidates and return it as the result.

  1. Create a hash map that stores the count of each number.
  2. Iterate over the sequence of numbers and populate the map with the count of each number.
  3. Initialize the result as -1.
  4. Iterate over the map and if the value of the key is 1, set result equal to the maximum of key or the current result.
  5. Return the result at the end.

COMPLEXITIES

Here n is the size of array.

TIme Complexity: O(n).
This is because we must insert every number into the hash map and insertion into a hash map is a constant time operation.

Space Complexity: O(n).
In the worst case, we will need to store all of the numbers with a frequency of 1

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
using namespace std;

int largestUniqueNumber(vector<int> &A) {
unordered_map<int, int> count;

// Store counts of each element
for (int &i : A) {
  count[i]++;
}

int result = -1;
for (auto it : count) {
	// If count of the integer is 1, get maximum.
	if (it.second == 1) {
	  result = max(result, it.first);
	}
}

return result;
}

int main() {
ios_base::sync_with_stdio(false);

int t,n,i;

cin>>t;

while(t--)
{
	cin>>n;
	vector<int> v(n);
	
	for(i=0;i<n;i++)
		cin>>v[i];
	
	cout<<largestUniqueNumber(v)<<endl;
}

return 0;
}
1 Like