UrbanPro
true

Find the best tutors and institutes for Java Training

Find Best Java Training Classes

Please select a Category.

Please select a Locality.

No matching category found.

No matching Locality found.

Outside India?

Search for topics

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

Lets Talk About Software Design-patterns
What are Design Patterns? Design Pattern is a used and tested solution for a known problem. In simple words, you can say a general reusable solution to a commonly occurring problem within a given context...

Lambda Expressions in Java
A lambda expression, introduced in Java 8 is similar to a block of code resembling an anonymous function that can be passed to constructors or methods for execution as an argument. Examples: a)() ->...

DBMS - SQL - Any/All
All - Operator SELECT empno, sal FROM emp WHERE sal > ALL (1999, 2999, 3999); Output of Above query is same as below query SELECT empno, sal FROM emp WHERE sal > 1999 AND sal > 2999...

Radhe Shyam | 02 Apr

0 0
0

JAVA - Object Cloning
JAVA - Object Cloning Is the way of creating the same copy of object without calling the class constructor. It means we can make any class object multiple times without calling its default constructor....

Gaurav Kothari | 16 Feb

1 0
0

JAVA OOPs Concepts (Object-Oriented Programming System)
JAVA OOPs Concepts (Object-Oriented Programming System) It is primarily having below crucial points. Without below essential points, we will never be able to achieve OOPs in java, PHP, C#, etc. Now let...

Gaurav Kothari | 16 Feb

1 0
0
X

Looking for Java Training Classes?

Find best tutors for Java Training Classes by posting a requirement.

  • Post a learning requirement
  • Get customized responses
  • Compare and select the best

Looking for Java Training Classes?

Find best Java Training Classes in your locality on UrbanPro

Post your learning requirement

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