👍Runtime 254 ms  Beats 100.00% of users with Go
Code\n\ntype MajorityChecker struct {\n    digits  int\n\tpresum  [][]int\n\tpos     map[int][]int \n}\n\n\nfunc Constructor(arr []int) MajorityChecker {\n    m
# Code\n```\ntype MajorityChecker struct {\n    digits  int\n\tpresum  [][]int\n\tpos     map[int][]int \n}\n\n\nfunc Constructor(arr []int) MajorityChecker {\n    mc := MajorityChecker{\n\t\tdigits:  15,\n\t\tpresum:  make([][]int, len(arr)+1),\n\t\tpos:     make(map[int][]int),\n\t}\n\n\tfor i := range mc.presum {\n\t\tmc.presum[i] = make([]int, mc.digits)\n\t}\n\n\tfor i := 0; i < len(arr); i++ {\n\t\tn := arr[i]\n\t\tif _, ok := mc.pos[n]; !ok {\n\t\t\tmc.pos[n] = make([]int, 0)\n\t\t}\n\t\tmc.pos[n] = append(mc.pos[n], i)\n\n\t\tfor j := 0; j < mc.digits; j++ {\n\t\t\tmc.presum[i+1][j] = mc.presum[i][j] + (n & 1)\n\t\t\tn >>= 1\n\t\t}\n\t}\n\n\treturn mc\n}\n\n\nfunc (mc *MajorityChecker) Query(left int, right int, threshold int) int {\n    ans := 0\n\tfor i := mc.digits - 1; i >= 0; i-- {\n\t\tcnt := mc.presum[right+1][i] - mc.presum[left][i]\n\t\tb := 1\n\t\tif cnt >= threshold {\n\t\t\tb = 1\n\t\t} else if right-left+1-cnt >= threshold {\n\t\t\tb = 0\n\t\t} else {\n\t\t\treturn -1\n\t\t}\n\t\tans = (ans << 1) + b\n\t}\n\n\tlist := mc.pos[ans]\n\tif list == nil {\n\t\treturn -1\n\t}\n\tL := mc.floor(list, left-1)\n\tR := mc.floor(list, right)\n\tif R-L >= threshold {\n\t\treturn ans\n\t}\n\treturn -1\n}\n\nfunc (mc *MajorityChecker) floor(list []int, n int) int {\n\treturn sort.Search(len(list), func(i int) bool {\n\t\treturn list[i] > n\n\t})\n}\n\n\n/**\n * Your MajorityChecker object will be instantiated and called as such:\n * obj := Constructor(arr);\n * param_1 := obj.Query(left,right,threshold);\n */\n```
['Go']