Beats 100% in Time and Memory | Bit Manipulation | Binary Search | Java
\n\n\n# Complexity\n- Time complexity:\nEach query will be answered in O(log(n))\n\n- Space complexity:\nO(1)\n\n# Code\n\nclass Solution {\n\n    long MAAAX = 
![Screenshot 2024-05-12 at 9.46.12 PM.png](https://assets.leetcode.com/users/images/47305508-f5c7-4804-91be-924fcabc8bca_1715532328.2991083.png)\n\n\n# Complexity\n- Time complexity:\nEach query will be answered in $$O(log(n))$$\n\n- Space complexity:\n$$O(1)$$\n\n# Code\n```\nclass Solution {\n\n    long MAAAX = 1000000000000000L;\n\n    // this fn counts sum of powers of 2 in multiplication of powerful arrays from 0 to (2^n -1)\n    long getMult(int n) {\n        if (n <= 0)\n            return 0L;\n\n        long tmp = ((long) n * (n + 1)) / 2L;\n\n        long pp = (long) Math.pow(2, n);\n\n        return pp * tmp;\n    }\n\n    // this fn counts len of big_nums if we concate powerful arrays from 0 to (2^n -1)\n    long getLen(int n) {\n        long pp = (long) Math.pow(2, n - 1);\n        return pp * (long) n;\n    }\n\n    // counts total sum of power of 2 and total on bits in n\n    int[] getMaxSum(long n) {\n        int tot = 0;\n        int on = 0;\n\n        for (int i = 0; i < 64; i++) {\n            boolean x = (n & 1) == 1;\n            n = n >> 1;\n\n            if (x) {\n                tot += i;\n                on++;\n            }\n\n        }\n\n        return new int[] { tot, on };\n    }\n\n    // counts sum of power of 2 for big_nums array of 0 to n\n    long countMult(long n) {\n        int[] maxSum = getMaxSum(n);\n        int totSum = maxSum[0];\n\n        long multB = (long) totSum;\n\n        for (int i = 0; i < 64; i++) {\n\n            boolean x = (n & 1) == 1;\n            n = n >> 1;\n\n            if (x) {\n                totSum -= i;\n\n                long tmp1 = (long) Math.pow(2, i);\n                long tmp2 = (long)totSum * tmp1;\n                long tmp3 = getMult(i - 1);\n                long tmp4 = tmp2 + tmp3;\n\n\n                multB += tmp4;\n            }\n\n        }\n\n        return multB;\n    }\n\n   // counts len of big_nums array of 0 to n\n    long countLen(long n) {\n        int[] maxSum = getMaxSum(n);\n        int totOn = maxSum[1];\n\n        long onBits = (long) totOn;\n\n        for (int i = 0; i < 64; i++) {\n\n            boolean x = (n & 1) == 1;\n            n = n >> 1;\n\n            if (x) {\n                totOn -= 1;\n\n                long tmp1 = (long) Math.pow(2, i);\n                long onTmp2 = (long)totOn * tmp1;\n                long onTmp3 = getLen(i);\n                long onTmp4 = onTmp2 + onTmp3;\n\n                onBits += onTmp4;\n            }\n\n        }\n\n        return onBits;\n    }\n\n    // find max n for which big_array(0 to n) length is equal or just smaller than target\n    long bs(long target) {\n        long l = 0L, r = MAAAX;\n\n        while (l < r) {\n            long mid = (l + r + 1) / 2L;\n\n            long len = countLen(mid);\n\n            if (len > target) {\n                r = mid - 1;\n            } else {\n                l = mid;\n            }\n\n        }\n\n        long finalLen = countLen(l);\n        long finalMult = countMult(l);\n\n        if (finalLen == target)\n            return finalMult;\n\n        // add remaining power of 2 from next number if len < target\n        long nn = l + 1L;\n        for (int i = 0; i < 64; i++) {\n            boolean x = (nn & 1) == 1;\n            nn = nn >> 1;\n\n            if (x) {\n                finalMult += (long) i;\n                finalLen += 1L;\n            }\n\n            if (finalLen == target)\n                return finalMult;\n        }\n\n        return -1;\n    }\n\n    // modular power of 2 with mod p\n    long power(long x, long y, long p) {\n\n        if(y == 0L) return 1L%p;\n\n        long res = 1L;\n\n        x = x % p;\n\n        if (x == 0L)\n            return 0L;\n\n        while (y > 0L) {\n\n            if ((y & 1) != 0L)\n                res = (res * x) % p;\n\n            y = y >> 1;\n            x = (x * x) % p;\n        }\n\n        return res;\n    }\n\n    public int[] findProductsOfElements(long[][] queries) {\n\n        \n        int[] ans = new int[queries.length];\n\n\n        for(int i=0; i<queries.length; i++)\n        {\n            long mult1 = bs(queries[i][0]);\n            long mult2 = bs(queries[i][1]+1);\n\n            ans[i] = (int)(power(2L,mult2-mult1,queries[i][2]));\n\n            System.out.println(mult1+":"+mult2+":"+ans[i]);\n\n        }\n\n        return ans;\n\n    }\n}\n```
['Binary Search', 'Bit Manipulation', 'Java']