[JAVA] BEATS 100.00% MEMORY/SPEED 0ms // APRIL 2022
\n\tclass MajorityChecker {\n    \n    private final int digits=15;\n    private int[][]presum;\n    private ArrayList[]pos;\n    \n    public MajorityChecker(i
\n\tclass MajorityChecker {\n    \n    private final int digits=15;\n    private int[][]presum;\n    private ArrayList<Integer>[]pos;\n    \n    public MajorityChecker(int[] arr) {\n        int len=arr.length;\n        presum=new int[len+1][digits];\n        pos=new ArrayList[20001];\n        \n        for(int i=0;i<len;i++){\n            int n=arr[i];\n            if(pos[n]==null)pos[n]=new ArrayList();\n            pos[n].add(i);\n            \n            for(int j=0;j<digits;j++){\n                presum[i+1][j]=presum[i][j]+(n&1);\n                n>>=1;\n            }\n        }\n    }\n    \n    public int query(int left, int right, int threshold) {\n        int ans=0;\n        for(int i=digits-1;i>=0;i--){\n            int cnt=presum[right+1][i]-presum[left][i];\n            int b=1;\n            if(cnt>=threshold)b=1;\n            else if(right-left+1-cnt>=threshold)b=0;\n            else return -1;\n            ans=(ans<<1)+b;\n        }\n        \n        // check\n        ArrayList<Integer>list=pos[ans];\n        if(list==null)return -1;\n        int L=floor(list,left-1);\n        int R=floor(list,right);\n        if(R-L>=threshold)return ans;\n        return -1;\n    }\n    \n    private int floor(ArrayList<Integer>list,int n){\n        int left=0, right=list.size()-1, mid;\n        while(left<=right){\n            mid=left+(right-left)/2;\n            int index=list.get(mid);\n            if(index==n)return mid;\n            else if(index<n)left=mid+1;\n            else right=mid-1;\n        }\n        return right;\n    }\n    }
['Java']