[Java] Two Approaches - 1) By Bit Manipulation 2) Segment Tree and Binary Search
By finding the Possible Candidate by counting the number of bits at each position\n\nclass MajorityChecker {\n    private HashMap<Integer, List<Integer>> valueM
**By finding the Possible Candidate by counting the number of bits at each position**\n```\nclass MajorityChecker {\n    private HashMap<Integer, List<Integer>> valueMap;\n    private int[][] preBit;\n    \n    public MajorityChecker(int[] arr) {\n        this.valueMap = new HashMap<>();\n        this.preBit = new int[arr.length][16]; // Count the number of ones till the index for each bit position\n        \n        for(int i=0; i<arr.length; i++){\n            valueMap.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);\n        }\n        \n        for(int i=0; i<arr.length; i++){\n            for(int j=0; j<16; j++){\n                int bitVal = (arr[i] >> j) & 1;\n                preBit[i][j] = ( i >= 1 ? preBit[i-1][j] : 0 ) + bitVal;\n            }\n        }\n    }\n    \n    public int query(int left, int right, int threshold) {\n        // Find the candidate value which can be the majority element\n        int candVal = 0;\n        for(int i=0; i<16; i++){\n            int countOne = preBit[right][i] - ( left >= 1 ? preBit[left-1][i] : 0);\n            if(countOne >= threshold){\n                candVal = (candVal | (1 << i));\n            }\n        }\n        \n        // Check if the candVal is the majority element \n        List<Integer> valIndexList = valueMap.get(candVal);\n        if(valIndexList == null || valIndexList.size() < threshold || valIndexList.get(valIndexList.size()-1) < left) return -1;\n        \n        // Find the left and the right index of the candVal in the list to know the frequency\n        int leftIndex = findPosByBinarySearch(valIndexList, left);\n        int rightIndex = findPosByBinarySearch(valIndexList, right);\n        if(rightIndex == valIndexList.size() || valIndexList.get(rightIndex) != right) rightIndex -= 1;\n        \n        return rightIndex - leftIndex + 1 >= threshold ? candVal : -1;\n    }\n    \n    private int findPosByBinarySearch(List<Integer> li, int key){\n        int l = 0;\n        int h = li.size();\n        \n        while(l < h){\n            int m = l + (h-l)/2;\n            if(li.get(m) < key) l = m+1;\n            else h = m;\n        }\n        \n        return l;\n    }\n}\n\n/**\n * Your MajorityChecker object will be instantiated and called as such:\n * MajorityChecker obj = new MajorityChecker(arr);\n * int param_1 = obj.query(left,right,threshold);\n */\n```\n\n**By Segment Tree**\n```\nclass MajorityChecker {\n    private int[] nums;\n    private SegmentTree treeRoot;\n    private HashMap<Integer, List<Integer>> valueMap;\n    \n    public MajorityChecker(int[] arr) {\n        this.nums = arr;\n        this.valueMap = new HashMap<>();\n        \n        // Create the valueMap to store the list of the indexes for each value \n        for(int i=0; i<arr.length; i++){\n            valueMap.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);\n        }\n        \n        this.treeRoot = new SegmentTree(arr);\n    }\n    \n    public int query(int left, int right, int threshold) {\n        // Get the majority element from the Segment Tree\n        int candVal = treeRoot.getMajorityElement(left, right);\n        \n        // Check if the candVal is the majority element \n        List<Integer> valIndexList = valueMap.get(candVal);\n        if(valIndexList == null || valIndexList.size() < threshold || valIndexList.get(valIndexList.size()-1) < left) return -1;\n        \n        // Find the left and the right index of the candVal in the list to know the frequency\n        int leftIndex = findPosByBinarySearch(valIndexList, left);\n        int rightIndex = findPosByBinarySearch(valIndexList, right);\n        if(rightIndex == valIndexList.size() || valIndexList.get(rightIndex) != right) rightIndex -= 1;\n        \n        return rightIndex - leftIndex + 1 >= threshold ? candVal : -1;\n    }\n    \n        private int findPosByBinarySearch(List<Integer> li, int key){\n        int l = 0;\n        int h = li.size();\n        \n        while(l < h){\n            int m = l + (h-l)/2;\n            if(li.get(m) < key) l = m+1;\n            else h = m;\n        }\n        \n        return l;\n    }\n    \n    // Segment Tree Class to do all the operations related to Segment Tree \n    private class SegmentTree{\n        private SegmentTreeNode treeRoot;\n        \n        public SegmentTree(int[] nums){\n            this.treeRoot = createSegmentTree(0, nums.length - 1, nums);\n        }\n        \n        // Create segment tree from a given array\n        private SegmentTreeNode createSegmentTree(int s, int e, int[] nums){\n            if(s == e){\n                return new SegmentTreeNode(s, e, new Pair(nums[s], 1));\n            }\n            \n            int m = s + (e-s)/2;\n            SegmentTreeNode root = new SegmentTreeNode(s, e, null);\n            root.leftChild = createSegmentTree(s, m, nums);\n            root.rightChild = createSegmentTree(m+1, e, nums);\n            \n            // Merge the pairs of the right and left child\n            root.pair = mergePairOfRightAndLeftChild(root.leftChild.pair, root.rightChild.pair);\n            \n            return root;\n        }\n        \n        // Return the merged pair of the left and right child \n        private Pair mergePairOfRightAndLeftChild(Pair leftPair, Pair rightPair){\n            if(leftPair.val == rightPair.val){\n                return new Pair(leftPair.val, leftPair.vote + rightPair.vote);\n            }\n            \n            // Left is the majority for because of greater votes\n            if(leftPair.vote > rightPair.vote){\n                return new Pair(leftPair.val, leftPair.vote - rightPair.vote);\n            }\n            \n            return new Pair(rightPair.val, rightPair.vote - leftPair.vote);\n        }\n        \n        // Return the majority element\n        public int getMajorityElement(int left, int right){\n            return queryTree(treeRoot, left, right).val;\n        }\n        \n        // Query tree to return the majority element\n        private Pair queryTree(SegmentTreeNode root,int start, int end){\n            if(start <= root.start && root.end <= end){\n                return root.pair;\n            }\n            \n            int mid = root.start + (root.end - root.start)/2;\n            Pair res = new Pair(0, 0);\n            if(start <= mid){\n                res = mergePairOfRightAndLeftChild(res, queryTree(root.leftChild, start, end));\n            }\n            if(mid < end){\n                res = mergePairOfRightAndLeftChild(res, queryTree(root.rightChild, start, end));\n            }\n            \n            return res;\n        }\n        \n        private class SegmentTreeNode{\n            public int start;\n            public int end;\n            public SegmentTreeNode leftChild;\n            public SegmentTreeNode rightChild;\n            public Pair pair;\n            \n            public SegmentTreeNode(int start, int end, Pair pair){\n                this.start = start;\n                this.end = end;\n                this.pair = pair;\n            }\n        }\n        \n        // To store the value and the Moore\'s vote \n        private class Pair{\n            public int val;\n            public int vote;\n            \n            public Pair(int val, int vote){\n                this.val = val;\n                this.vote = vote;\n            }\n        }\n    }\n}\n\n/**\n * Your MajorityChecker object will be instantiated and called as such:\n * MajorityChecker obj = new MajorityChecker(arr);\n * int param_1 = obj.query(left,right,threshold);\n */\n```
[]