Ex-Amazon explains a solution with a video, Python, JavaScript, Java and C++
My youtube channel - KeetCode(Ex-Amazon)\nI create 165 videos for leetcode questions as of May 7, 2023. I believe my channel helps you prepare for the coming te
# My youtube channel - KeetCode(Ex-Amazon)\nI create 165 videos for leetcode questions as of May 7, 2023. I believe my channel helps you prepare for the coming technical interviews. Please subscribe my channel!\n\n### Please subscribe my channel - KeetCode(Ex-Amazon) from here.\n\n**I created a video for this question. I believe you can understand easily with visualization.** \n\n**My youtube channel - KeetCode(Ex-Amazon)**\nThere is my channel link under picture in LeetCode profile.\nhttps://leetcode.com/niits/\n\n![FotoJet (68).jpg](https://assets.leetcode.com/users/images/74d2fabc-7764-4586-ba70-1a70902e5b44_1683403496.6128898.jpeg)\n\n\n---\n\n# Intuition\nSort input array and Use two pointers. When we create subsequences, we have two choices. including each number and excluding each number.\n\n# Approach\nThis is based on Python code. Other languages might be different.\n\n1. Sort the given array of integers \'nums\' in non-descending order using the \'sort()\' method of Python.\n\n2. Initialize two pointers, \'left\' and \'right\', pointing to the first and the last element of the sorted array, respectively.\n\n3. Initialize a variable \'ans\' to zero, which will store the number of subsequences that satisfy the given sum condition.\n\n4. Define a constant \'mod\' and assign it a value of 10^9 + 7.\n\n5. Use a while loop to iterate until \'left\' becomes greater than \'right\'.\n\n6. Check if the sum of the current left and right elements of \'nums\' is greater than \'target\'.\n\n7. If the sum is greater, decrement \'right\' by 1 to exclude the largest element and try again.\n\n8. If the sum is less than or equal to \'target\', then increment \'left\' by 1 to exclude the smallest element, and calculate the number of possible subsequences between \'left\' and \'right\'.\n\n9. For calculating the number of subsequences between \'left\' and \'right\', use the \'pow()\' function to calculate 2 raised to the power of \'right - left\' modulo \'mod\', and add the result to \'ans\'.\n\n10. After the while loop terminates, return the value of \'ans\' modulo \'mod\'.\n\n---\n\n**My youtube channel - KeetCode(Ex-Amazon)**\nThere is my channel link under picture in LeetCode profile.\nhttps://leetcode.com/niits/\n\n---\n\n# Complexity\nThis is based on Python code. Other languages might be different.\n\n- Time complexity: O(n log n)\nn is the length of the input array nums. This is because the nums.sort()\n\n- Space complexity: O(1)\nwe only use a constant amount of extra space to store the pointers and variables\n\n# Python\n```\nclass Solution:\n    def numSubseq(self, nums: List[int], target: int) -> int:\n        nums.sort()\n        left, right = 0, len(nums) - 1\n        ans = 0\n        mod = 10 ** 9 + 7\n\n        while left <= right:\n            if nums[left] + nums[right] > target:\n                right -= 1\n            else:\n                # pow(x, y, z) = x^y % z\n                ans += pow(2, right - left, mod)\n                left += 1\n        \n        return ans % mod\n```\n# JavaScript\n```\n/**\n * @param {number[]} nums\n * @param {number} target\n * @return {number}\n */\nvar numSubseq = function(nums, target) {\n    let pow = [];\n    pow.push(1);\n\n    nums.sort((a, b) => { return a - b; })\n\n    const mod = 1e9+7;\n\n    for (let i = 1; i < nums.length; i++) {\n        pow.push((pow[pow.length - 1] * 2) % mod);\n    }\n\n    let left = 0, right = nums.length - 1, res = 0;\n\n    while (left <= right) {\n        if (nums[left] + nums[right] > target) {\n            right--;\n        } else {\n            res = (res + pow[right - left]) % mod;\n            left++;\n        }\n    }\n\n    return res;\n};\n\n\n```\n# Java\n```\nclass Solution {\n    public int numSubseq(int[] nums, int target) {\n        Arrays.sort(nums);\n        int[] pow = new int[nums.length];\n        pow[0] = 1;\n\n        for (int i = 1; i < nums.length; i++) {\n            pow[i] = (pow[i - 1] * 2) % 1000000007;\n        }\n\n        int left = 0, right = nums.length - 1;\n        int res = 0;\n\n        while (left <= right) {\n            if (nums[left] + nums[right] > target) {\n                right--;\n            } else {\n                res = (res + pow[right - left]) % 1000000007;\n                left++;\n            }\n        }\n\n        return res;    \n    }\n}\n```\n# C++\n```\nclass Solution {\npublic:\n    int numSubseq(vector<int>& nums, int target) {\n        sort(nums.begin(), nums.end());\n        int n = nums.size();\n        vector<int> pow(n, 1);\n        const int mod = 1e9 + 7;\n        \n        for(int i = 1; i < n; i++){\n            pow[i] = (2 * pow[i-1]) % mod;\n        }\n        \n        int left = 0, right = n-1;\n        long long res = 0;\n        \n        while(left <= right){\n            if(nums[left] + nums[right] > target){\n                right--;\n            } else {\n                res = (res + pow[right - left]) % mod;\n                left++;\n            }\n        }\n        \n        return res;\n    }\n};\n```
['C++', 'Java', 'Python3', 'JavaScript']