Write a program that finds the majority element in an array if it exists. Majori

Question

Write a program that finds the majority element in an array if it exists. Majority element is the element which appears in more than half of the array locations. Declare an array of size 7 and read the array elements from the user. Then, compute and print the majority element if it exists. In an array of size 7. an element has to appear in at least 4 array locations in order to be majority element. Consider the following example. Majority element in this array Is 3 since 3 appears 4 times and array size is 7 (0-6). Sample execution of the program for this array is given below Enter 7 numbers 3 2 3 3 2 3 1 Majority = 3 In some cases majority element does not exist. Following example shows this. There is no majority element in this array. Maximum count in the array is 2. However. 4 is needed for majority. Sample execution of the program is given below Enter 7 numbers 1 2 2 3 4 3 1 No Majority One approach to this problem Is to count how many times each element appears in the array. Find the maximum occurrence and compare it with 4. If maximum occurrence in the array is > 4 then corresponding element is majority. If maximum occurrence is

Explanation / Answer

A Linear Time Majority Vote Algorithm

This algorithm, which Bob Boyer and I invented in 1980 decides which element of a sequence is
in the majority, provided there is such an element. How would you determine the majority
element of:
sequence: A A A C C B B C C C B C C
You could count the number of occurrences of each element
S1:
A A A C C B B C C C B C C
^
?:0
We will sweep down the sequence starting at the pointer position shown above.

As we sweep we maintain a pair consisting of a current candidate and a counter. Initially,
the current candidate is unknown and the counter is 0.

When we move the pointer forward over an element e:

If the counter is 0, we set the current candidate to e and we set the counter to 1.
If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate.
When we are done, the current candidate is the majority element, if there is a majority.

S2:
A A A C C B B C C C B C C
^
A:1
S3:
A A A C C B B C C C B C C
^
A:2
[Step]

S4:
A A A C C B B C C C B C C
^
A:3
[Step]
.....

A A A C C B B C C C B C C
^
C:3
The majority element is C (if any element has a majority).
Note that if you replaced the first C with an A, above, the algorithm would still end with C
being chosen, but in fact C would not be the majority element: there is no majority in the
modified list.

MajorityElement.java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
* @author Srinivas Palli
*
*/
public class MajorityElement {

   /**
   * @param args
   */
   public static void main(String[] args) {
       // TODO Auto-generated method stub
       int[] nums = new int[7];
       Scanner scanner = new Scanner(System.in);
       System.out.println("Enter 7 Numbers:");
       for (int i = 0; i < 7; i++) {
           nums[i] = scanner.nextInt();

       }

       List<Integer> result = majorityElement(nums);
       if (result.size() > 0) {
           System.out.println("Mojority = " + result.get(0));
       } else {

           System.out.println("No Mojority");
       }

   }

   /**
   * to caliculate majority votes using linear voting system
   * @param nums
   * @return
   */
   public static List<Integer> majorityElement(int[] nums) {
       List<Integer> result = new ArrayList<Integer>();

       Integer n1 = null, n2 = null;
       int c1 = 0, c2 = 0;

       for (int i : nums) {
           if (n1 != null && i == n1.intValue()) {
               c1++;
           } else if (n2 != null && i == n2.intValue()) {
               c2++;
           } else if (c1 == 0) {
               c1 = 1;
               n1 = i;
           } else if (c2 == 0) {
               c2 = 1;
               n2 = i;
           } else {
               c1--;
               c2--;
           }
       }

       c1 = c2 = 0;

       for (int i : nums) {
           if (i == n1.intValue()) {
               c1++;
           } else if (i == n2.intValue()) {
               c2++;
           }
       }

       if (c1 > nums.length / 3)
           result.add(n1);
       if (c2 > nums.length / 3)
           result.add(n2);

       return result;
   }

}

Enter 7 Numbers:
3 2 3 3 2 3 1
Mojority = 3

Enter 7 Numbers:
1 2 2 3 4 3 1
No Mojority

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.