UrbanPro
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

Problem Description Task.

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
Follow 0

Please Enter a comment

Submit

Other Lessons for You

Priority in TestNG
public class Priority { @Test (priority=1)public void login() {System.out.println("login");} @Testpublic void email1() {System.out.println("email1");} @Test (priority=-2)public void email2() {System.out.println("email2");} //I...

Sarthak C. | 22/11/2021

0 0
0

Example of DependsOnMethod in TestNG
public class dependsonM { @Test public void login() { System.out.println("login"); } @Test (dependsOnMethods = {"login"}) public void email() { //Intentionally I am failing this testcase Assert.assertTrue(false);...

Sarthak C. | 18/11/2021

0 0
0

TestNG Annotations and its sequence
public class TestNGAnnotations { @BeforeMethod public void beforeM() { System.out.println("Before Method"); } @AfterMethod public void afterMethod() { System.out.println("After Method"); } @BeforeClass...

Sarthak C. | 18/11/2021

0 0
0

ListIterator Example
public class ListIteratorEx { public static void main(String args) { List<String> li = new ArrayList<String>(); li.add("java1"); li.add("java2"); li.add("java3"); li.add("java4"); ListIterator...

Sarthak C. | 18/11/2021

0 0
0

doWhile example in Java
public class doWhilePracticleEx { public void test() { } public static void main(String args) { String q1 = "Who is PM of India?"; String a1 = "Sonia Gandhi"; String a2 = "Rahul Gandhi"; String a3...

Sarthak C. | 18/11/2021

0 0
0
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

Book a Free Demo

This website uses cookies

We use cookies to improve user experience. Choose what cookies you allow us to use. You can read more about our Cookie Policy in our Privacy Policy

UrbanPro.com is India's largest network of most trusted tutors and institutes. Over 55 lakh students rely on UrbanPro.com, to fulfill their learning requirements across 1,000+ categories. Using UrbanPro.com, parents, and students can compare multiple Tutors and Institutes and choose the one that best suits their requirements. More than 7.5 lakh verified Tutors and Institutes are helping millions of students every day and growing their tutoring business on UrbanPro.com. Whether you are looking for a tutor to learn mathematics, a German language trainer to brush up your German language skills or an institute to upgrade your IT skills, we have got the best selection of Tutors and Training Institutes for you. Read more