C# O(Log N) memory, beats 100% by memory
Intuition\nIn this problem, in order to compute powers of 2 for big exponents, most solutions use $O(N)$ memory to store each power of $2$ up to $N$ - length of
# Intuition\nIn this problem, in order to compute powers of 2 for big exponents, most solutions use $O(N)$ memory to store each power of $2$ up to $N$ - length of `nums` array. This could be greatly optimizied, if we store only those powers which itself are powers of $2$, eg $2^1, 2^2, 2^4, 2^8 \\ldots$ and so on. And later use this powers to quickly compute any power of $2$. To get the idea, consider this example: \n\n$$2^{15} = 2^1 \\cdot 2^2 \\cdot 2^4 \\cdot 2^8$$\n\n# Approach\nGeneral approach here is similar to other solutions:\n- Sort the `nums` array\n- Use 2 pointers `min` and `max` as lower and upper bound, and increase/decrease correspondingly until they meet. \n\n# Complexity\n- Time complexity: $$O(N \\log N)$$ - this is required by Sorting.\n\n- Space complexity: $$O(\\log N)$$ - additional space for selected powers of 2\n\n# Code\n```csharp\npublic class Solution {\n    const int Mod = 1000_000_007;\n    long[] powersOf2 = BuildPowersOf2();\n    \n    public int NumSubseq(int[] nums, int target) {\n        long total = 0;\n        \n        Array.Sort(nums);\n\n        if (nums[0] > target) return 0;\n\n        // initially min and max indexes consider whole array\n        int min = 0, max = nums.Length - 1;\n\n        while (min <= max)\n        {\n            if (nums[min] + nums[max] > target) // <-- bigger than target\n                max--;                          // <-- decrease upper bound estimate\n            else {\n                // here we fit the target, increase total count\n                total = (total + ToPowerOf2(max - min)) % Mod; // 2^(max - min)\n                min++; // <-- current lower bound is used, try increase it\n            }\n        }\n        \n        return (int)total;\n    }\n\n    long ToPowerOf2(int e) {\n        if (e < 31) return 1 << e; // 2^(e)\n\n        // one of optimal ways to calculate powers of 2 for big exponents\n        // to get the idea, consider this example: 2^15 = 2^1 * 2^2 * 2^4 * 2^8\n        long pow = 1;\n        int i = 0;\n\n        while (e > 0) {\n            if ((e & 1) == 1) pow = pow * powersOf2[i] % Mod;\n            i++;\n            e >>= 1;\n        }\n\n        return pow;\n    }\n\n    static long[] BuildPowersOf2() {\n        var powers = new long[17]; // enough to cover all powers up to 2^100_000\n\n        powers[0] = 2;\n\n        for (int i = 1; i < powers.Length; i++)\n            powers[i] = powers[i - 1] * powers[i - 1] % Mod;\n            \n        return powers;\n    }\n}\n```
['C#']