Java beats 100%
Java beats 100%\n\n\n\n\n# Code\n\nclass MajorityChecker {\n\nprivate final int digits=15;\nprivate int[][]presum;\nprivate ArrayList<Integer>[]pos;\n\npublic M
Java beats 100%\n\n![image.png](https://assets.leetcode.com/users/images/e09d2a27-8110-4a48-b58c-ffcb9870f502_1716292190.7768798.png)\n\n\n# Code\n```\nclass MajorityChecker {\n\nprivate final int digits=15;\nprivate int[][]presum;\nprivate ArrayList<Integer>[]pos;\n\npublic 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\npublic 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\nprivate 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}\n```
['Java']