JAVA CODE || Properly Explained With Diagram || Modified Two Sum Approach ||
Intuition\n Describe your first thoughts on how to solve this problem. \nwe can use modified two sum approach to solve this.\n\n# Approach\n Describe your appro
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nwe can use modified two sum approach to solve this.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFirstly we need to ensure that the array is sorted for this approach to work.\nNow we create a new array of the same size as the input array, this array stores the power of 2 , \neg- [$$2^0$$, $$2^1$$, $$2^2$$, $$2^3$$, $$2^4$$ and so on ]\n\n\n    powerValues = [1, 2, 4, 8, 16...]\n    \n`(powerValues[i - 1] * 2) % mod` is done to avoid integer overflow, the dry run for filling the powerValues array is\n\n    at i = 0\n    powerValues[0] = 1\n\n    at i = 1\n    powerValues[1] = (powerValues[0] * 2) % (10^9 + 7)\n    i.e. powerValues[1] = 2\n\nnow we just modify the two sum approach to solve this question.\nlets consider - \n\n    arr - [3, 5, 6, 7]      target = 9\n           |     |\n         left   right\n\nsince `nums[left] + nums[right] <= target` then that means that we can find `2^(right- left)`different number of Subsequences which satisfy the above condition.\n\nwe got `2^(right- left)`different number of Subsequences because -\n`total number of ways to select n elements = 2 ^ n` this also includes those cases where we don\'t select any element and we aren\'t allowed to pick non-empty subsequences.\n\nso we fix the smallest element, then we only have the choice to select or not select those elements ranging from `left + 1` to `right`\n\n    eg - \n        arr - [1, 2, 6, 7]\n               |     |\n             left   right\n    \nif`1`is fixed, then we only have option for`2`, and `6` either to `select them` or `not select them`. So,\n\n`total number of ways to select n elements = 2 ^ (right - (left + 1) + 1)` (+ 1 at the end for 0 based indexing.)\n\nso instead of calculating all the number of Subsequences, we use the powerValues array to find number, then we modulo it with `10^9 + 7` to avoid integer overflow\n\n# Complexity\n- Time complexity:\nSorting - $$O(n*logn)$$\nSaving the power of 2 - $$O(n)$$\nModified Two Sum approach - $$O(n)$$\n\nOverall Time Complexity - $$O(n*logn)$$ + $$O(n)$$ + $$O(n)$$ = $$O(n*logn)$$\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\nclass Solution {\n    public int numSubseq(int[] nums, int target) {\n        // Sorting the array\n        Arrays.sort(nums);\n        int n = nums.length;\n        \n        int[] powerValues = new int[n];\n        int mod = (int) 1e9 + 7;\n\n        // Filling the array with power of 2\'s\n        for(int i = 0; i < n; i++) {\n            powerValues[i] = i == 0 ? 1 : (powerValues[i - 1] * 2) % mod;\n        }\n\n        // Modified Two sum approach\n        int left = 0;\n        int right = n - 1;\n        int counter = 0;\n\n        while(left <= right) {\n            if(nums[left] + nums[right] > target) {\n                right--;\n            } else {\n                // Using the stored value of power of 2\n                // to find the number of Subsequences\n                counter = (counter + powerValues[right - left]) % mod;\n                left++;\n            }\n        }\n\n        return counter;\n    }\n}\n```
['Java']