Hey, there codeforces.
This blog is specially related to Java programmers who submit their code mainly in Java through the contest. I recently came across a question where you were needed to create an array and find an element appearing thrice. There are two very simple solutions to this question.
Approaches:
- Create a Hashmap, iterate through the array, and check if the map contains the key, if not add else put it in the map and key to (count +1 ) After putting the values in the map, iterate the map using map.keyset() function and check if the key value is >= 3, if yes then print the value else print -1.
Pseudo code —
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
int x = in.nextInt();
int count = map.get(x) == null ? 0 : map.get(x);
map.put(x, count + 1);
}
for (Integer i: map.keySet()) {
if (map.get(i) >= 3) {
System.out.println(i);
return;
}
}
System.out.println("-1");
- Create an array and store the inputs in it. sort the array using the standard
Arrays.sort()
function. Iterate the array and count the frequency of any element appearing >= 3 times, break the loop and print the number else print -1. This is a relatively simpler approach but with a catch. If you create an int array, you might end up getting TLE. The reason behind this is that the Arrays.sort() function uses the Quick Sort technique for sorting the elemental array such asint[] arr
, and the worst-case time complexity of Quick Sort isO(n^2)
. on the other hand if we create anInteger[] array
i.e. int type object array then the function uses Merge Sort to sort the array and its worst-case time complexity isO(nlog(n))
.
Pseudo code —
Integer arr[]=new Integer[(int)n];
for (int i=0;i<n ;i++ )
arr[i]=sc.nextInt();
boolean flag=false;
Arrays.sort(arr);
if(n<3)
System.out.println(-1);
else
{for(int i=0;i<n-2;i++)
{
if(arr[i].equals(arr[i+1]) && arr[i+1].equals(arr[i+2]))
{System.out.println(arr[i]);
flag=true;
break;}
}
if(flag==false)
System.out.println(-1);}
Of course, there are other relevant approaches to this problem too, such as using StringTokenizer or creating a different array of size n+1. But this was the area where I got stuck with the WA which forced me to change my approach. This could have been avoided if one knew this earlier. Thanks for giving your valuable time reading this. Hope it helps ))
My Submission: 161264708