[Python3][Binary Search] + Bit ordering || Illustration || 800ms
Intuition\n Describe your first thoughts on how to solve this problem. \nLet\'s break down the problem.\nFor each query, we have start, end, and modulus.\n- If 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nLet\'s break down the problem.\nFor each query, we have start, end, and modulus.\n- If we had a function that for a given number would give us the frequencies of the the power of 2 in the big nums array from index 0 to the queried index, we could answer each query\n- Indeed, given this function, we would query (start-1) and end, take the difference of the 2 dictionaries, and then compute each result\n- So how to compute the frequency dictionary given a position ; i.e. return the frequency of each power of 2 in big nums from 0 up to n ; this is what the problem is all about\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nHow to compute this frequency dictionary ?\nFor this, the main intuition is to notice a pattern in the distribution of power of 2s when you list all integers consecutively.\nBelow are listed the binary representation of numbers from 0 to 20:\n\n| Integer | Bit 4 | Bit 3 | Bit 2 | Bit 1 | Bit 0 |\n| ------- | ----- | ----- | ----- | ----- | ----- |\n| 0       | 0     | 0     | 0     | 0     | 0     |\n| 1       | 0     | 0     | 0     | 0     | 1     |\n| 2       | 0     | 0     | 0     | 1     | 0     |\n| 3       | 0     | 0     | 0     | 1     | 1     |\n| 4       | 0     | 0     | 1     | 0     | 0     |\n| 5       | 0     | 0     | 1     | 0     | 1     |\n| 6       | 0     | 0     | 1     | 1     | 0     |\n| 7       | 0     | 0     | 1     | 1     | 1     |\n| 8       | 0     | 1     | 0     | 0     | 0     |\n| 9       | 0     | 1     | 0     | 0     | 1     |\n| 10      | 0     | 1     | 0     | 1     | 0     |\n| 11      | 0     | 1     | 0     | 1     | 1     |\n| 12      | 0     | 1     | 1     | 0     | 0     |\n| 13      | 0     | 1     | 1     | 0     | 1     |\n| 14      | 0     | 1     | 1     | 1     | 0     |\n| 15      | 0     | 1     | 1     | 1     | 1     |\n| 16      | 1     | 0     | 0     | 0     | 0     |\n| 17      | 1     | 0     | 0     | 0     | 1     |\n| 18      | 1     | 0     | 0     | 1     | 0     |\n| 19      | 1     | 0     | 0     | 1     | 1     |\n| 20      | 1     | 0     | 1     | 0     | 0     |\n\nBit 0 alternates with a periodicity of 2 (0 then 1) etc\nBit 1 alternates with a periodicity of 4 (0 0 1 1 ) etc\nBit 2 alternates with a periodicity of 8 (0 0 0 0 1 1 1 1 ) etc\netc\n\nso for a given integer n, to compute the number of entries in the big nums array than come before it you can apply the following formula:\nfor each bit in binary representation of the integer:\n- compute how many period fit before the integer, and multiply the number of period by the size of the period // 2\n- for the last part if any (truncated period), if the truncated part is more than half the period, and the difference, i.e. truncated_part - (period // 2)\nThis gives you the frequency dictionary for big nums for all integers between 0 and n\nPlease note : you need to adapt the integer and add 1, since we start at 0\n\n**Example with 18 (need to increase by 1 so 19)**\nBinary representation : 10010\nBit 0 : period length 2; 1s per period : 1 ; nb full periods : 19 // 2 = 9 ; truncated_period : 19 % 2 == 1 ; frequency : 9 * 1 + 0\nBit 1 : period length 4, 1s per period : 2 ; nb full periods : 19 // 4 = 4 ; truncated_period : 3 ; frequency : 4 * 2 + 3 - (4//2) = 9\netc.\n\n\nBut we want something slightly different, we want the frequency dictionary for entries between 0 and and index i, not the number of entries of big nums for all integers from 0 to n\nWe need to introduce binary search here:\nBinary search from 1 to index (this is a reasonable upper limit), each time querying the number of entries the candidate integer yields, this allows you to find the integer which is at the limit of the index you are interested in (that yields just below the number of entries that you are interested in).\n\nIf this integer yields too few values, add to the frequency dictionary entries from the next integer until you have enough entries in bignums array.\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(q * (log n)^2) \nFor each query:\nwe need to binary search of start and end\neach binary search is takes O(log n) computation to determine number of previous entries in the big nums array\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n0(q log (n))\nwe need to store the frequency dictionary\n\n\n# Code\n```\nclass Solution:\n    \n    def findProductsOfElements(self, queries: List[List[int]]) -> List[int]:\n        \n        #helper function 1 : to compute freq dictionary given integer\n        def compute_integer(n):\n            res = dict()\n            n += 1\n            f = format(n, \'b\')\n\n            for i in range(len(f)):\n                period = pow(2,i+1)\n                full_periods = n // period\n                res[i] = full_periods * (period//2)\n                rest = n % period\n                to_add = rest - (period // 2)\n                if to_add > 0:\n                    res[i] += to_add\n            \n            return res\n        \n        #helper function 2 : binary search to find correct integer given position requested\n        def binary_search_integers(index):\n\n            lower = 1\n            upper = index\n\n            while lower <= upper:\n\n                x = (lower + upper) // 2\n                tmp = compute_integer(x)\n                total_freq = sum((v for v in tmp.values()))\n\n                if total_freq == index:\n                    upper = x\n                    break\n\n                if total_freq < index:\n                    lower = x +1\n                else:\n                    upper = x-1\n        \n            res = compute_integer(upper)\n            total_freq = sum((v for v in res.values()))\n            if total_freq == index:\n                return res\n            \n            extra = format(upper+1, \'b\')[::-1]\n            for i in range(len(extra)):\n                if extra[i] == \'1\':\n                    res[i] += 1\n                    total_freq += 1\n                    if total_freq == index:\n                        return res\n        \n        res = []\n        for si,ei,modi in queries:\n            tmp = 1\n            d_start = binary_search_integers(si)\n            d_end = binary_search_integers(ei+1)\n\n            for k,v in d_start.items():\n                d_end[k] -= v\n\n            for k,v in d_end.items():\n                tmp *= pow(pow(2,k,modi),v, modi)\n            \n            res.append(tmp % modi)\n        \n        return res\n    \n\n\n```
['Python3']