[ C++ ] | Binary Search + Binary Exponentiation | Easy Explanation
Intuition\n Describe your first thoughts on how to solve this problem. \nSince we have to find Subsequences, Sorting will not hamper the result\n\nFor each inte
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSince we have to find Subsequences, Sorting will not hamper the result\n\nFor each integer if we found the maximum value which can be accepted under the given conditions we can find all subsequences starting from that integer.\n\n# Prerequisites \n\n[ Binary Exponentiation](https://leetcode.com/problems/powx-n/)\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSort the Array,then for each element find the maximum accepted value\n\nwe only have to consider those cases where `target-nums[currIndex]>=nums[currIndex]` because then only we can find a possible answer\n\n\n\n## How will Upper Bound work\nUpper bound will return the index of the element which is just    greater than the maximum accepted value\n\nIf Upper Bound returns `currIndex` means that there is no integer `>` nums[currIndex] we have to skip those case.\n\nOtherwise calculate the all the subsequences\n\nNo. of Subsequences will be `2^(Length of array)`\n\n\n\n# Complexity\n- Time complexity: $$O(nLogn)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n#define ll long long\nclass Solution {\npublic:\n    // Define a constant M for modular arithmetic\n    int M = 1e9+7;\n    \n    // Define a function for efficient modular exponentiation\n    ll binpow(ll a, ll b) {\n        ll res = 1;\n        while (b > 0) {\n            if (b & 1)\n                res = (res * a)%M;\n            a = (a * a)%M;\n            b >>= 1;\n        }\n        return res;\n    }\n    \n    int numSubseq(vector<int>& nums, int target) {\n        int n = nums.size();\n        int ans  = 0;\n        \n        // Sort the input array\n        sort(nums.begin(), nums.end());\n\n        // Iterate over each element of the array\n        for(int i = 0;i<n;i++){\n            int currIndex = i;\n            \n            // If the current element is less than or equal to half the target\n            if(target-nums[currIndex]>=nums[currIndex]){\n                \n                // Use upper_bound to find the index of the largest element in the array\n                // that is less than or equal to the target minus the current element\n                int index = upper_bound(nums.begin()+currIndex, nums.end(), (target-nums[currIndex]))-nums.begin();\n                \n                // If such an element exists\n                if(index!=currIndex){\n                    \n                    // Compute the number of subsequences that can be formed using the current\n                    // element and all elements up to and including the target minus the current element\n                    ans = ans%M+ binpow(2, (index-1-currIndex))%M;\n                }\n            }\n        }\n        \n        return ans;\n    }\n};\n\n```
['Binary Search', 'Sorting', 'C++']