Java very easy O(nlogn) solution
Intuition\n Describe your first thoughts on how to solve this problem. \n- We will use two pointer approach to solve this, it is same as two sum\n- Suppose we g
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- We will use two pointer approach to solve this, it is same as two sum\n- Suppose we got index i & j such that nums[i] + nums[j] <= target. Then no of subsequence will be 2^(j-i).\n- In order to get i & j & apply two pointer we need to have array in sorted order. \n- This will not affect no of subsequence as 3,6,5 & 3,5,6 will have same no of subsequence.\n- Now for above statement\n- like - a=[3,5,6] t=9\n-  3 & 6 satisfy the condition ie 3+6<=9, no of subsequence will be 2^(3-1)=4\n- 3 * _ * _ , 3 * 5 * _, 3 * _ * 6, 3 * 5 * 6\n- For each no we have two option either we can take it or leave it\n- we add this subsequence count in the result for each valid pair and get the final result.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- 2^(j-i) will take O(n) computation time we can reduce it through binary exponentiation\n- 1st method\n- 2^n , 2^5\n- if n is odd\n- n * 2^(n-1) , 2 * 2^4\n- if n is even\n- n * n * 2^(n/2); , 2 * 2 * 2^2\n- we can compute 2^n in O(logn) time.\n- through pre computation\n- 2nd method\n- store the prev result and compute next\n- pows[0] = 1 ,2^0 = 1\n- pows[1] = pows[0] * 2, 2^1 = 2\n- pows[2] = pows[1] * 2, 2^2 = 4\n- it will take O(1) time, we need not compute 2^n everytime just return res at index n.\n- two-pointers\n- l+r>t\n- r-- to reduce the sum\n- else l++ to compute other nos.\n- if we start r again from end for each l++ then it would always be greater than target bcs array is sorted.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n- O(nlogn) -> sorting\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n- O(n) -> pre-computation\n\n# Code\ncredits @lee215\n```\nclass Solution {\n    public int numSubseq(int[] nums, int target) {\n        \n        Arrays.sort(nums);\n        int res=0, n=nums.length, l=0, r=n-1, mod=(int)1e9+7;\n        int[] pows=new int[n];\n        pows[0]=1;\n        for(int i=1; i<n; i++)\n            pows[i]=pows[i-1]*2%mod;\n        while(l<=r) {\n            if(nums[l]+nums[r]>target)\n                r--;\n            else\n                res= (res+pows[r-l++])%mod;\n        }\n        return res;\n    }\n}\n```
['Array', 'Two Pointers', 'Sorting', 'Java']