c++ and JAVA sorting + two pointer with explanation
Intuition\n Describe your first thoughts on how to solve this problem. \nhere arr[i] means sum of 2^i + 2^(i-1) + ....2^2 + 2^1 + 1\nThis is just to make the ca
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nhere arr[i] means sum of 2^i + 2^(i-1) + ....2^2 + 2^1 + 1\nThis is just to make the calculations easier.\nWe will soon understand that since the subsequences can be generated using any no irrespective of their place but should be in order in which it appears in the array but a catch here is that since we are just concerned about the min and max element in the subsequence so, whatever the order we arrange it in (in the order in which it appears or in sorted order) does not matter until the no. are same.\nFor Example,\n[7,6,3,5]\nnow sort->[3,5,6,7]\nthe subsequences including 7->(max) and 3->(min) can be easily created using any of the no lieing bw them like \n3,7\n3,6,7\n3,5,7\n3,5,6,7\nfor now assume target to be 10\nnow all these subseq can also be generated int the org array but with diff orders\nlike\n7,3\n7,6,3\n7,3,5\n7,6,3,5\nlook the no of subseq are always the same or we can say that same subsets will be generated from both org and sort arrays\nSo, now we just have to find every pair whose sum <=target and take into account all the subseq formed by elements lienng in bw these pairs lets say nums[i] and nms[j] then all elements bw i...j will create sub this no can be fetched by 2^(no of elem in bw ie; j-i-1) considering every no as present in subseq or not.\nLets say these elem as x\nnow any elem >nums[i] int the right of iand before j will also sum with nums[j] to <target so all those no will also create these sub for that instead of doing their add ups sep we can just add the sum of 2^x +2^(x-1) + 2^(x-2)  +--=4+2+1. This is the reason for above arr[i];\nnow a asimple two pointer apprach isused to get those pairs i & j in sorted nums if i & j makes a pair dd its cont and then i++ try bigger i\'s inc the sum if it is greater than target j-- dec the sum \nOne spl case single element becoming min and max of the subseq including themselves is separately taken care of.\nAll the multiplications by 2 can be changed with <<1 to make it more fast as shift operations are faster than multi. operations and long long is also not needed , testcases are such that ans never goes above INT_MAX during any adds.  \n\n  \n# Approach\n<!-- Describe your approach to solving the problem. -->\nsorting + two approach\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(nlog(N))\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n\n**PLS UPVOTE IF IT HELPED!**\n\n# JAVA\n```\nclass Solution {\n    public int numSubseq(int[] nums, int target) {\n        int mod=1000000007;\n        Arrays.sort(nums);\n        int n=nums.length;\n        int ans=0;\n        if(2*nums[0]<=target) ans++;\n        if(n==1) return ans;\n        int[] arr=new int[n];\n        arr[0]=1;\n        for(int i=1;i<n;i++){\n            if(2*nums[i]<=target) ans++;\n            arr[i]=(((arr[i-1]+1)*2)-1)%mod;\n        }\n        int i=0;\n        int j=n-1;\n        while(i<j){\n            if(nums[i]+nums[j]<=target){\n                ans+=arr[j-i-1];\n                ans%=mod;\n                i++;\n            }else{\n                j--;\n            }\n        }\n        return ans;\n    }\n}\n```\n# C++\n```\nclass Solution {\npublic:\n    int numSubseq(vector<int>& nums, int target) {\n        int mod=1e9+7;\n        sort(nums.begin(),nums.end());\n        int n=nums.size();\n        long long ans=0;\n        if(2*nums[0]<=target) ans++;\n        if(n==1) return ans;\n        int* arr=new int[n];\n        arr[0]=1;\n        arr[1]=3;\n        if(2*nums[1]<=target) ans++;\n        for(int i=2;i<n;i++){\n            if(2*nums[i]<=target) ans++;\n            arr[i]=((1LL*(arr[i-1]+1)*2)-1)%mod;\n        }\n        int i=0;\n        int j=n-1;\n        while(i<j){\n            if(nums[i]+nums[j]<=target){\n                ans+=arr[j-i-1];\n                ans%=mod;\n                i++;\n            }else{\n                j--;\n            }\n        }\n        return ans;\n    }\n};\n```
['C++']