Beats 99.7% || C++ || Significance of 'int' and 'long long'  || Binary Search
\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nTo start, we arrange the numbers in the nums array in ascending order. This helps 
\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nTo start, we arrange the numbers in the nums array in ascending order. This helps us navigate through the array more effectively.\n\nWe place i at the beginning of the array and j at the end.\n\nAs we move forward with the pointers, we keep track of how many valid subsequences we encounter. For each position of i, we move j backwards while adding up the numbers at nums[i] and nums[j]. This helps us find subsequences where the sum meets our condition.\n\n**The number of subsequences of length \\(j - i\\) is given by \\(2^{j - i - 1}\\). This can be understood using a simple observation. When constructing a subsequence of length \\(j - i\\), each element has two choices: either include it in the subsequence or exclude it. This binary choice applies to each element in the subsequence, resulting in a total of \\(2^{j - i}\\) possible subsequences of length \\(j - i\\). However, since we are counting subsequences where element at i should be included for sure, we subtract one to obtain \\(2^{j - i - 1}\\) as the final count.**\n\nNote :-\nTo make our calculations faster and more accurate, we use a trick with powers of 2.This allows us to efficiently count the number of subsequences without getting into complex calculations.\n\nThroughout our process, we make sure our calculations don\'t become too large by applying modular arithmetic. This means we only keep the remainder when dividing by a certain number, which helps us avoid big and unwieldy numbers.\n\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:O(n) {Assuming given arrays are already sorted.}\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int numSubseq(vector<int>& nums, int target) {\n        sort(nums.begin(), nums.end());\n        int n = nums.size();\n        const int MOD = 1e9 + 7;\n        long long ans = 0;\n        int i = 0;\n        int j = n - 1;  \n\n        vector<long long> powers(n);\n        powers[0] = 1;\n        for (int k = 1; k < n; ++k) {\n            powers[k] = (powers[k - 1] * 2) % MOD;\n        }\n\n        while (i <= j) {\n            if (nums[i] + nums[j] <= target) {\n                ans = (ans + powers[j - i]) % MOD;\n                i++;\n            } else {\n                j--;\n            }\n        }\n\n        return ans;\n    }\n};\n\n```
['Two Pointers', 'Binary Search', 'C++']