Java Clean Solution | BiWeekly Contest
Code\n\n// class Solution {\n\n//     private long getProduct(int[] arr) {\n//         long prod = 1;\n//         for (int i = 0; i < arr.length; i++) {\n//    
# Code\n```\n// class Solution {\n\n//     private long getProduct(int[] arr) {\n//         long prod = 1;\n//         for (int i = 0; i < arr.length; i++) {\n//             prod *= arr[i];\n//         }\n//         return prod;\n//     }\n\n//     public int[] findProductsOfElements(long[][] queries) {\n//         int lmt = 1015;\n//         int[][] pow2 = new int[lmt + 1][];\n//         for (int i = 1; i <= lmt; i++) {\n//             PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());\n//             long sum = 0;\n//             for (int p = 1; p <= 30; p++) {\n//                 if ((1 << p) > i) {\n//                     break;\n//                 }\n//                 pq.add(1 << p);\n//                 sum += (1 << p);\n//             }\n\n//             int size = pq.size();\n//             int[] arr = new int[size];\n//             for (int j = 0; j < size; j++) {\n//                 arr[j] = pq.poll();\n//             }\n//             pow2[i] = arr;\n//         }\n\n//         int[] res = new int[queries.length];\n//         for (int i = 0; i < queries.length; i++) {\n//             long[] query = queries[i];\n//             long fi = query[0];\n//             long toi = query[1];\n//             long prod = 1;\n//             for (long k = fi; k <= toi; k++) {\n//                 prod *= getProduct(pow2[(int) k]);\n//                 prod %= (int) query[2];\n//             }\n//             res[i] = (int) prod;\n//         }\n//         return res;\n//     }\n// }\n\n\nclass Solution {\n    public int[] findProductsOfElements(long[][] queries) {\n        // for (int val = 0; val < 10; val++) System.out.println(val+" has "+countOnes(val)+" ones filled.");\n        int[] res = new int[queries.length];\n        for (int i = 0; i < res.length; i++) res[i] = fulfil(queries[i]);\n        return res;\n    }\n    private int fulfil(long[] query) {\n        long from = query[0]; long to = query[1]; long mod = query[2];\n        long[] upTo = upTo(to);\n        long[] littler = upTo(from - 1);\n        // System.out.println(to+": "+Arrays.toString(upTo));\n        // System.out.println((from - 1)+": "+Arrays.toString(littler));\n        long res = 1;\n        long pow = 1;\n        for (int i = 0; i < 63; i++) {\n            long amt = upTo[i] - littler[i];\n            if (amt == 0) {\n                pow = (pow * 2) % mod;\n                continue;\n            }\n            long mult = modPow(1l << i, amt, mod);\n            res = (res * mult) % mod;\n            pow = (pow * 2) % mod;\n            if (res == 0) return 0;\n        }\n        return (int) res;\n    }\n    private long modPow(long base, long pow, long mod) {\n        if (pow == 0) return 1;\n        long lesser = modPow(base, pow / 2, mod);\n        lesser = (lesser * lesser) % mod;\n        if (pow % 2 == 1) lesser = (lesser * base) % mod;\n        return lesser;\n    }\n    private long[] upTo(long maxIndex) {\n        long minVal = 0, maxVal = maxIndex + 5;\n        long highest = 0, excess = maxIndex + 1;\n        while (minVal <= maxVal) {\n            long midVal = minVal + (maxVal - minVal) / 2;\n            long amtOfOnes = countOnes(midVal);\n            // System.out.println(midVal+": "+amtOfOnes);\n            if (amtOfOnes < maxIndex + 1) {\n                highest = midVal;\n                excess = maxIndex + 1 - amtOfOnes;\n                minVal = midVal + 1;\n            } else if (amtOfOnes > maxIndex + 1) {\n                maxVal = midVal - 1;\n            } else {\n                highest = midVal;\n                excess = 0;\n                break;\n            }\n        }\n        // System.out.println("For "+maxIndex+" index, I pick value: "+highest+" with "+excess+" extra ones.\\n");\n        long[] bitCounts = grab(highest);\n        if (excess == 0) return bitCounts;\n        long higher = maxVal + 1;\n        for (int p = 0; p < 64; p++) {\n            if ((higher & (1l << p)) != 0) {\n                bitCounts[p]++;\n                if (--excess == 0) return bitCounts;\n            }\n        }\n        return bitCounts;\n    }\n    public long[] grab(long n) {\n        long[] res = new long[64];\n        for (int p = 0; p < 64; p++) {\n            long totalPairs = (n + 1) / (1l << (p + 1));\n            res[p] += totalPairs * (1l << p);\n            long remainder = (n + 1) % (1l << (p + 1));\n            if (remainder > (1l << p)) res[p] += remainder - (1l << p);\n        }\n        return res;\n    }\n    public long countOnes(long max) {\n        long totalSetBits = 0;\n        long n = max + 1;\n        for (long p = 0; (1l << p) <= max; p++) {\n            long totalPairs = n / (1l << (p + 1));\n            totalSetBits += totalPairs * (1l << p);\n            totalSetBits += (long) Math.max(0, n % (1l<< (p + 1)) - (1l << p));\n        }\n\n        return totalSetBits;\n    }\n}\n```\n\n---\n\n**C++**\n\n```\nclass Solution {\n\n    const int MOD = 1000000009;\n\npublic:\n    int cal(vector<int> big, int fi, int ti, int mi) {\n        int p = 1;\n        for (int i = fi; i <= ti; i++) {\n            p = (1ll * p * big[i]) % mi;\n        }\n        return p;\n    }\n\npublic:\n    vector<int> gen(int x) {\n        vector<int> pow;\n        int powe = 1;\n        while (x > 0) {\n            if (x & 1) {\n                pow.push_back(powe);\n            }\n            x >>= 1;\n            powe <<= 1;\n        }\n        return pow;\n    }\n\npublic:\n    vector<int> findProductsOfElements(vector<vector<long long>>& queries) {\n        vector<int> big;\n        for (int i = 1; i <= 100; i++) {\n            vector<int> pow = gen(i);\n            big.insert(big.end(), pow.begin(), pow.end());\n        }\n\n        vector<int> ans;\n        for (const auto& q : queries) {\n            int fi = q[0];\n            int ti = q[1];\n            int mi = q[2];\n            int res = cal(big, fi, ti, mi);\n            ans.push_back(res);\n        }\n        return ans;\n    }\n};\n```
['Array', 'Bit Manipulation', 'Bitmask', 'Java']