• Implement Majority-Element finding using Algorithm V from lecture slides
• Input:
• array of N positive integers – size of the problem is N n Output:
• 1) majority element (M.E.) – element occurring more than N/2 times

(order of elements doesn’t matter), if M.E. exists n 2) -1, if the majority element does not exist in the array

• Input should be read into array of integers: int[] (do not use

ArrayList) n The code should work on that array, without re-formatting the data e.g. into a linked list or any other data structure

• The algorithm should have O(N) time complexity n Use of any Java built-in functions/classes is NOT allowed n With the exception of functions from Scanner, System.in and

System.out (or equivalent) for input/output

Input-output formats

••

Input Format:– First line: a single integer number N>=1, N<=1,000,000– Following N lines: each contains a single positive integer containing the elements of the array• Each integer will be <=1,000,000,000– Input will always be correct w.r.t. the specification aboveOutput format:– A single line, with a single integer:

Input 1:511001001100Output 1:100

Input 2:4100002100003Output 2:-1

• -1 if the input array has no majority element
• X if integer X is the majority element of the input array

Algorithm V (from lecture)

3

3

4

7

7

7

7

7

7

7

8

• Observation: some pair of elements can be deleted from A without changing M.E. (if M.E. exists) – Example:
• Possible pairs and corresponding deletion effects:
  • (non-M.E., non-M.E.) -> result doesn’t change
  • (M.E., non-M.E.) -> result doesn’t change – (M.E., M.E.)-> result can change assuming M.E. exists
• Order in which pairs are deleted is not important
• But we don’t know which element is M.E.!

Algorithm V (from lecture)

• Solution:
  • Instead of Delete everything except (M.E., M.E.)
  • Do Delete everything except (X,X)
• Move through the elements from left to right
• Keep deleting pairs of no-equal elements at every opportunity

3

7

3

7

7

4

7

7

7

7

8

• E. will be the only one remaining – Easy implementation with double-linked list • Example:
  • But we can also do these concepts for an array.

How?

3

3

3

7

7

4

7

7

7

7

8

Algorithm V (from lecture)

• Array approach:
  • Assign a candidate-M.E. (c-ME) (init:1^st element)
  • As you sweep the array,
• do not delete c-ME, move forward
• delete a non-c-ME with one c-ME.
• If another element becomes most frequent in the array so far (i.e., a new c-ME), all instances of the previous one have already been deleted
  • One approach: keep current position and keep count of c-ME and decrease upon delete
• Location of c-MEs is not important, only their count

Algorithm V (from lecture)

• Boyer & Moore approach
  • Select first element as candidate M.E., set counter to 1 – Move forward through the array. When we see:
• another copy of the c-ME -> increase counter
• some other element -> decrease counter
• If the counter becomes 0, assign a new c-ME at current

index

• previous c-ME lost the chance
• Once the entire array is traversed, c-ME will be the only

element left (if exists)

Input/output in Java

• Use Standard I/O to read input and write the result
• For Java, input: System.in, output: System.out
• “Do Not”s
  • Do not read from a disk file/write to disk file
  • Do not write anything to screen except the result
• Ex: Human centric messages (“the result is”, “please enter..”)
• Automated grading via script will be used for checking correctness of your output