aleksandrrrrr's blog

By aleksandrrrrr, history, 21 month(s) ago, In English

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.

1669B - Triple

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 as int[] arr, and the worst-case time complexity of Quick Sort is O(n^2). on the other hand if we create an Integer[] array i.e. int type object array then the function uses Merge Sort to sort the array and its worst-case time complexity is O(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

  • Vote: I like it
  • +2
  • Vote: I do not like it

| Write comment?
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

good for me that I am not java user

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Don't use Integer, it is slower than primitive int and you will get TLE on other problems. Instead, shuffle the array before shorting and you will be fine.