Java 95% time O(Log(n)), Bit Count + Binary Search
The idea here is for each bit position, count how many number (in the given range) has this bit setted. We solve this using preffix count.\nThen, build a number
The idea here is for each bit position, count how many number (in the given range) has this bit setted. We solve this using preffix count.\nThen, build a number with those bits that count >= threshold (you can check that, if there is a number with the majority rule, all bits that count >= threshold belong to that number)\nLast, check if this number appears more or equals than "threshold" times on the given range, using Binary Search over the indexes of appearence of the number.\n\n\n```\n\nimport java.util.ArrayList;\nimport java.util.Collections;\nimport java.util.List;\n\nclass MajorityChecker {\n\n    int bits = 16;\n    int[][] count = null;\n    List<Integer>[] indexes = null;\n    int[] arr = null;\n    public MajorityChecker(int[] arr) {\n        this.arr = arr;\n        int max = 0;\n        for(Integer i : arr) max = Integer.max(max, i);\n        count = new int[arr.length][bits];\n        indexes = (List<Integer>[]) new ArrayList[max+1];\n        for(int i = 0; i < arr.length; i++) {\n            int val = arr[i];\n            int cp = val;\n            int idx = 0;\n            while(cp > 0) {\n                count[i][idx] += (cp % 2);\n                cp = cp >> 1;\n                idx++;\n            }\n            if(i > 0) for(int j = 0; j < bits; j++) count[i][j] += count[i-1][j];                \n                        \n            List<Integer> idxs = indexes[val];\n            if(idxs == null) indexes[val] = (idxs = new ArrayList<>());            \n            idxs.add(i);\n        }\n    }\n    \n    int parseInteger(int[] bi, int th) {\n        int num = 0;\n        for(int i = bits-1; i >= 0; i--) {\n            int count = bi[i];\n            if(count >= th) num += 1;            \n            if(i > 0) num = num << 1;\n        }\n        return num;\n    }\n    \n    public int query(int left, int right, int threshold) {\n        int[] num = count[right];\n        if(left != 0) {\n            int[] temp = new int[bits];\n            for(int i = 0; i < temp.length; i++) temp[i] = count[right][i] - count[left-1][i];            \n            num = temp;\n        }\n        \n        int val = parseInteger(num, threshold);\n        List<Integer> idx = indexes[val];\n        if(idx == null) return -1; \n        int li = Collections.binarySearch(idx, left);        \n        if(li < 0) {\n          li = -li-1;\n          if(li == idx.size() || idx.get(li) > right) return -1;\n        }\n        int ri = Collections.binarySearch(idx, right);\n        if(ri < 0) {\n          ri = -ri-1;\n          if(ri == idx.size() || idx.get(ri) > right) ri--;  \n        } \n        int size = (ri - li) + 1;\n        if(size >= threshold) return val;\n        return -1;\n    }\n}\n\n```
[]