C++ Easy Binary Search Solution
So let us first look at the logic part, so consider an array [2,3,4,5] and target value 7 for this array . Now we know that for the first element i.e., 2 the up
So let us first look at the logic part, so consider an array [2,3,4,5] and target value 7 for this array . Now we know that for the first element i.e., 2 the upper_bound value would be 5 (target-a[i]) . So we would add pow(2,3-0) in our answer (3 is index of 5 and 0 is index of 2). But the question arises why we considered all the subsequences with max length 3, why not 4, we all know that if we are considering a particular element then if we want any subsequence to satisy this condition of ***(max-min<=target)*** we would have to consider that element in every subsequence so originally if we would have take subsequences of max length 4 then there would be some subsequence like [3,4,5] which would have been taken into consideration but this subsequence does not have min value as 2 so therfore to eleminate such subsequences we have taken one length less than the actual length.\nFollow the below steps to get an idea on how to approach this question:\n1. Firstly we will Sort the array.\n1. After that we will compute and store the powers of 2 for values till 100001 with mod. \n1. Now we will perform binary search on every element to find the upper_bound of (target-a[i]). If we find any such value then we will add powers[ind-i] to our answer. Here we will make use of the powers array which we made in previous step.\n\n\n``` \nclass Solution {\npublic:\n    int numSubseq(vector<int>& a, int t) {\n        \n        sort(a.begin(),a.end());\n        \n        // powers array to precomputer powers of 2 with mod\n        int powers[100001]={};\n        \n        // pow(2,0)=1\n        powers[0]=1;\n        \n        int mod=1000000007;\n        \n        for(int i=1;i<100001;i++){\n            // calculating power for every i\n            powers[i]=(powers[i-1]*2)%mod;\n        }\n        \n        long long int ans=0;\n        \n        for(int i=0;i<a.size();i++){\n            \n            // defining ranges for every i\n            int l=i,r=a.size()-1,ind=-1;\n            \n            while(l<=r){\n                int mid=(l+r)/2;\n                \n                // if a[mid]+a[i]<=target then we can increase the value of l \n                if(a[mid]+a[i]<=t){\n                    ind=max(ind,mid);\n                    l=mid+1;\n                }\n                \n                // else we have to decrease value of r \n                else{\n                    r=mid-1;\n                }\n            }\n            \n            // edge case (if there is no such value (target-a[i]) does not exist then we will not compute for this i and every i greater than this one\n            if(ind!=-1){\n                \n \xA0 \xA0 \xA0 \xA0 \xA0 \xA0 \xA0 \xA0// subtract the value of i from ind and add the power to the answer \n                ind-=i;\n                \n                ans=(ans+powers[ind])%mod;\n                \n            }\n            \n            else{\n                break;\n            }\n        }\n        \n        return ans;\n    }\n};\n```\nIf you have liked my explanation for this question, then please ***upvote***. \nIf you have any ***doubts*** then you can ask in the comments section.\nHappy Coding!
['Binary Search', 'Sorting', 'Binary Tree']