Java Solution for Number of Sequences that Satisfy the Given Sum Condition Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe intuition behind the solution is to use a two-pointer approach to find all possible
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe intuition behind the solution is to use a two-pointer approach to find all possible subsequences of the input array nums whose minimum and maximum elements sum up to a value less than or equal to the target.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe approach is to first sort the input array in ascending order. Then, initialize an array pow2 to store the powers of 2 modulo 109 + 7. The program then uses two pointers left and right to iterate through the array. The left pointer starts at the beginning of the array, and the right pointer starts at the end of the array.\nThe program then checks if the sum of the minimum and maximum element of the subsequence formed by the left and right pointers is less than or equal to the target. If it is, the program adds the number of possible subsequences that can be formed by the left and right pointers to the answer. The number of possible subsequences is calculated using the pow2 array. If the sum of the minimum and maximum element of the subsequence is greater than the target, the program moves the right pointer one position to the left. If the sum is less than or equal to the target, the program moves the left pointer one position to the right.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe time complexity of the solution is O(n log n), where n is the length of the input array. This is because the program sorts the input array, which takes O(n log n) time. The two-pointer approach then takes O(n) time to find all possible subsequences.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity of the solution is O(n), where n is the length of the input array. This is because the program uses an array pow2 of size n to store the powers of 2 modulo 109 + 7.\n\n# Code\n```\nclass Solution {\n    public int numSubseq(int[] nums, int target) {\n        Arrays.sort(nums);\n        int n = nums.length;\n        int mod = 1000000007;\n        int[] pow2 = new int[n];\n        pow2[0] = 1;\n        for (int i = 1; i < n; i++) \n        {\n            pow2[i] = pow2[i - 1] * 2 % mod;\n        }\n        int ans = 0;\n        int left = 0, right = n - 1;\n        while (left <= right) \n        {\n            if (nums[left] + nums[right] > target) \n            {\n                right--;\n            } \n            else \n            {\n                ans = (ans + pow2[right - left]) % mod;\n                left++;\n            }\n        }\n        return ans;\n    }\n}\n```
['Java']