❌Majority Element(Contest)

Majority Element easy Time Limit: 2 sec Memory Limit: 128000 kB

Problem Statement :

Given an array A of N elements. Find the majority element in the array. A majority element in an array A of size N is an element that appears more than N/2 times in the array. Input The first line of the input contains T denoting the number of testcases. The first line of the test case will contains the size of array N and second line will be the elements of the array.

Constraints: 1 <= T <= 100 1 <= N <= 10^5 1 <= A[i] <= 10^6

Sum of "N" over all testcases does not exceed 10^6 Output For each test case the output will be the majority element of the array. Output "-1" if no majority element is there in the array. Example Sample Input: 2 5 3 1 3 3 2 3 1 2 3

Sample Output: 3 -1

Explanation: Testcase 1: Since, 3 is present more than N/2 times, so it is the majority element. Testcase 2: Since, each element in {1, 2, 3} appears only once so there is no majority element.

link:https://my.newtonschool.co/playground/code/0vg1b87yni4x/

```java
import java.util.*;

public class Main {
    public static int findMajorityElement(int[] arr) {
        int n = arr.length;
        Map<Integer, Integer> freq = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int x = arr[i];
            freq.put(x, freq.getOrDefault(x, 0) + 1);
            if (freq.get(x) > n / 2) {
                return x;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
            }
            int majority = findMajorityElement(arr);
            System.out.println(majority);
        }
    }
}
```