KCE_0006-Editorial

editorial
, , , ,
1

Titanic
stable array or not
Setter : harijey
Tester : rohinth_076
Editorialist: ki_shore5

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

Arya Stark is interested in playing with numbers. So, now She is testing the array is Stable or Not. An array is said to be stable if it satisfy the following codition. Take an Example Case i: array a = [4,1,2,3,4,3,4,3,1,3] . In this array

  • 1 repeats 2 times
  • 2 repeats 1 times
  • 3 repeats 4 times
  • 4 repeats 3 times

In the above given example the value 1 repeats twice (2 times) so here the value 2 should satisfy the condition of replicating only once(1 time) this is similar in the case of the values of 3 and 4 .

Case ii: An array a = [1,1,1,3,3] This array is not stable because here the value 1 is replicated thrice(3 times) wherein the case of the value 3 it is replicated twice(2 times) but according to the given constrains the value 3 should be replicated only once(1 time)

Input Format

  • First line will contain NN, number of elements in the array.
  • Second line will contains N elements.

Output Format

Print “YES” if the array is stable , otherwise Print “NO”

Sample Input 1

10
4 1 2 3 4 3 4 3 1 3

Sample Output 1

Yes

Sample Input 2

5
1 1 1 3 3

Sample Output 2

NO

EXPLANATION:

  • The given problem statement explains the condition on which the array can be called as “STABLE”.
  • So to the concept we use here to find the frequencies of each of the array element is HASHING and storing the frequencies as values in the hashmap and the array elements as the keys in the hashmap.
  • Now the condition to be checked is that the value for a key stored in the hashmap has the corresponding key as its frequency in the array (ie. when 2 occurs 3 times . Then 3 should occur 2 times).
  • If this condition holds good for all the elements of the given array it is stable.

TIME COMPLEXITY:

O(n) for each test case , where ‘n’ is the number of elements in the given array.

SOLUTION:

import java.io.;
import java.util.;
class Solution{
static Scanner fs = new Scanner(System.in);
static PrintWriter out = new PrintWriter(System.out);

public static void main(String[] args) {
    
   int n = fs.nextInt();
   int[] a = new int[n];
   for(int i=0;i<n;i++)
   		a[i] = fs.nextInt();
   Map<Integer,Integer> m = new HashMap<>();
   
   for(int i:a)
     m.merge(i,1,Integer::sum);
   boolean flag = true;
   for(Map.Entry<Integer,Integer> i:m.entrySet())
        if(i.getKey() != m.getOrDefault(i.getValue(),0)){
            flag = false;
            break;
        }
   if(flag)
    out.println("YES");
    else
    out.println("NO");
   out.flush();
	
}

}