Easy Solution | C++ | Two pointer | Exponentiation | Beginner Friendly
\n\n# Approach\n- First, we sort the array.\n- We use the 2 pointer approach to check if the first and last element is greater or less than the target\n- If the
\n\n# Approach\n- First, we sort the array.\n- We use the 2 pointer approach to check if the first and last element is greater or less than the target\n- If the condition is satisfied then we calculate the number of non-empty subsequences\n- Number of sequences is equal to 2^n where n is the difference b/w the first and the last pointer\n- We calculate the power using Exponentiation to avoid TLE as it uses logn complexity.\n\n\n# Complexity\n- Time complexity:\nO(nlogn)\n\n- Space complexity: \nO(1)\n\n# Code\n```\nclass Solution {\nprivate:\n    long long power(long long base,long long n, long long mod){\n        long long ans=1;\n        while(n!=0){\n            if(n%2==1){\n                ans=(ans*base)%mod;\n                n--;\n            }else{\n                base=(base*base)%mod;\n                n=n/2;\n            }\n        }\n        return ans;\n    }\npublic:\n    int numSubseq(vector<int>& nums, int target) {\n\n        int start=0;\n        int end=nums.size()-1;\n\n        sort(nums.begin(),nums.end());\n\n        int mod=1000000007;\n\n        int count=0;\n\n        //number of subsequences is 2^n here, n is the range b/w the first and last element index\n\n        while(start<=end){\n\n            if(nums[start]+nums[end]<=target){\n                long long totalsubseq=power(2,end-start,mod);\n                count=(count+totalsubseq)%mod;\n                start++;\n            }\n            else{\n                end--;\n            }\n\n        }\n\n        return count;\n    }\n};\n```
['Two Pointers', 'C++']