true

Learn Java Training from the Best Tutors

• Affordable fees
• 1-1 or Group class
• Flexible Timings
• Verified Tutors

Search in

# Finding a Majority Element

Paras Chawla
29/05/2017 0 0

The goal in this code problem is to check whether an input sequence contains a majority element.

Input Format. The first line contains an integer, the next one contains a sequence of non-negative integers 0, 1, . . . ,−1. Constraints. 1 ≤ ?? ≤ 10^5 ; 0 ≤ ???? ≤ 10^9 for all 0 ≤ ?? < ??.

Output Format. Output 1 if the sequence contains an element that appears strictly more than??/2 times, and 0 otherwise.

Pseudo code

findCandidate(a[], size)

1. Initialize index and count of majority element

maj_index = 0, count = 1

1. Loop for i = 1 to size – 1

(a) If a[maj_index] == a[i]

count++

(b) Else

count--;

(c) If count == 0

maj_index = i;

count = 1

1. Return a[maj_index]

Java Code

import java.util.Scanner;

// Moore - Voting algorithm . Run-time complexity O(n)

public class MajorityElement {

public static void main(String[] args) {

Scanner scan = new Scanner(System.in);

int n = scan.nextInt();

long array[] = new long[n];

for (int i = 0; i < n; i++)

array[i] = scan.nextLong();

long candidate = findCandidate(array, n);

System.out.println(candidate);

int count = 0;

for (int i = 0; i < n; i++)

if (array[i] == candidate)

count++;

if (count > (n / 2))

System.out.println("1");

else

System.out.println("0");

}

static long findCandidate(long array[], int n) {

int index = 0;

long count = 1;

for (int i = 1; i < n; i++) {

if (array[index] == array[i])

count++;

else

count--;

if (count == 0)

{index = i;

count = 1;}

}

return array[index];

}

}

Output:

10

2 124554847 2 941795895 2 2 2 2 792755190 756617003

2

1

0 Dislike

## Other Lessons for You

As everyone knows for understanding any subject in detail we have go through the basics of that subject. But sometimes we tend to forget the basics which are required for the advanced subjects. So knowing...

01 Introduction to Digital Logic
Introduction to Digital logic:

Program Implementation
To implement a program, a student must understand the fundamental programming constructs of the language, as well as the design of the program. Object-oriented development involves implementing the individual...

Introduction to Programming Languages
What is a Programming Language? A programming language is a formal computer language or constructed language designed to communicate instructions to a machine, particularly a computer. Programming languages...

A Look at the State of Connected Devices in 2017
The connected devices trend is one that seems to be growing at a faster rate each year. This calendar year will be no different, as more and more companies continue to get involved. But where exactly do...

### Looking for Java Training Classes?

Learn from Best Tutors on UrbanPro.

Are you a Tutor or Training Institute?

Join UrbanPro Today to find students near you

X

### Looking for Java Training Classes?

The best tutors for Java Training Classes are on UrbanPro

• Select the best Tutor
• Book & Attend a Free Demo
• Pay and start Learning

### Learn Java Training with the Best Tutors

The best Tutors for Java Training Classes are on UrbanPro