Boyer-Moore-Voting

import java.util.*;

public class Main {
    public static int boyerMooreVotingAlgorithm(int[] nums) {
        int n = nums.length;

        // Step 1: Find the majority candidate
        int candidate = nums[0];
        int count = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i] == candidate) {
                count += 1;
            } else if (count == 0) {
                candidate = nums[i];
                count = 1;
            } else {
                count -= 1;
            }
        }

        // Step 2: Verify the majority candidate
        count = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == candidate) {
                count += 1;
            }
        }

        if (count > n / 2) {
            return candidate;
        } else {
            return -1;
        }
    }

    public static void main(String[] args) {
        int[] nums = {2, 2, 1, 1, 1, 2, 2};
        int majority = boyerMooreVotingAlgorithm(nums);
        if (majority != -1) {
            System.out.println("Majority element: " + majority);
        } else {
            System.out.println("No majority element found.");
        }
    }
}