New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Majority Element

Contributed by

Prashant Thakur

Last Updated: 20 Jan, 2023

Easy

0/40

Avg time to solve 15 mins

Success Rate 70 %

4 upvotes

Problem Statement

Given an array ‘A’ of ‘N’ integers, find the majority element of the array.

A majority element in an array ‘A’ of size ‘N’ is an element that appears more than floor(N / 2) times.

Note: The floor function returns the largest possible integer value which is equal to the value or smaller than that. It is guaranteed that there is always a majority element in the array ‘A’.

Example:

Input: ‘N’ = 9 ‘A’ = [2, 2, 1, 3, 1, 1, 3, 1, 1]

Output: 1

Explanation: The frequency of ‘1’ is 5, which is greater than floor(N / 2), 
hence ‘1’ is the majority element.

Detailed explanation ( Input/output format, Notes, Images )

Input Format

The first line contains one integer ‘N’, denoting the number of elements in the 
Array ‘A’.

The second line contains ‘N’ integers denoting the elements of the array ‘A’.

Output format:

Return the majority element.

Note:-

You don't need to print anything. Just implement the given function.

Constraints:

1 <= N <= 1e3
-1e9 <= A[i] <= 1e9

Time Limit: 1-sec

Sample Input 1:

9
2 2 1 3 1 1 3 1 1

Sample Output 1:

Explanation Of Sample Input 1:

Input: ‘N’ = 9, ‘A’ = [2, 2, 1, 3, 1, 1, 3, 1, 1]

Output: 1

Explanation: The frequency of ‘1’ is 5, which is greater than floor(N / 2), hence ‘1’ is 
The majority element.

Sample Input 2:

1
4

Sample Output 2:

Sample Input 3:

5
-53 75 56 56 56

Sample Output 3:

Autocomplete

Console