C++ solution using Binary Search | with detailed explanation on Time complexity
Complexity\n- Time complexity: O(log(P) * m log n)\n Add your time complexity here, e.g. O(n) \n\nfindmaxIndex and findminIndex: Both use binary search, which h
# Complexity\n- Time complexity: O(log(P) * m log n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\nfindmaxIndex and findminIndex: Both use binary search, which has a time complexity of O(log n), where n is the size of nums2. These functions are called for each element in nums1, so the overall complexity for both combined is O(m log n), where m is the size of nums1 and n is the size of nums2.\n\ncountProdLessEqualMid: It iterates through each element in nums1 and performs a binary search for each element in nums2. Therefore, its time complexity is O(m log n), where m is the size of nums1 and n is the size of nums2.\n\nkthSmallestProduct: It performs binary search on the range of possible products. In each iteration of the binary search, it calls countProdLessEqualMid, which has a time complexity of O(m log n). The binary search is performed until the range is exhausted. Therefore, the overall time complexity of kthSmallestProduct is O(log(P) * m log n), where P is the difference between the maximum and minimum possible products.\n\nThe dominant factor in the time complexity is the binary search operation, and the overall complexity can be expressed as O(log(P) * m log n).\n\n- Space complexity: O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe overall space complexity is dominated by the constant amount of extra space used in the functions, and it does not depend on the input size. Hence, the space complexity of the entire code is O(1).\n\n# Code\n```\nclass Solution {\npublic:\n    int findmaxIndex(vector<int>& nums2, long long  val, long long productNeeded){\n        long long low = 0, high = nums2.size()-1;\n        long long resIndex = -1;\n\n        while(low <= high){\n            long long mid = (low + high) / 2;\n            long long productObtained = nums2[mid] * val;\n\n            if(productObtained <= productNeeded)    resIndex = mid, low = mid + 1;\n            else                                    high = mid - 1;   \n        }\n        return resIndex + 1;\n    }\n    int findminIndex(vector<int>& nums2, long long  val, long long productNeeded){\n        long long low = 0, high = nums2.size()-1;\n        long long resIndex = nums2.size();\n\n        while(low <= high){\n            long long mid = (low + high) / 2;\n            long long productObtained = nums2[mid] * val;\n\n            if(productObtained <= productNeeded)    resIndex = mid, high = mid - 1;  \n            else                                    low = mid + 1;\n        }\n        return nums2.size() - resIndex;\n    }\n    \n    // countProdLessEqualMid(x) - how many products are less or equal than x.\n    long long countProdLessEqualMid(vector<int>& nums1, vector<int>& nums2, long long product){\n        long long count = 0;\n        for(int num : nums1){\n            if(num == 0  &&  product >= 0)   count += nums2.size(); \n            else if(num > 0)                 count += findmaxIndex(nums2, num, product);\n            else if(num < 0)                 count += findminIndex(nums2, num, product);\n        }\n        return count;\n    }\n\n    long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, long long k) {\n        \n        long long low = -1e10, high = 1e10; // Search space = min product to max product (-1e10 to +1e10)\n        while(low <= high){                 // Binary search - find the first moment where we have exactly k products\n            long long mid = (low + high) / 2;\n            if(countProdLessEqualMid(nums1, nums2, mid) >= k)       high = mid - 1;\n            else                                                    low = mid + 1;\n        }\n        return low;\n    }\n};\n\n\n// If num=0: (num * each element in nums2) = 0. all products <= midProduct. So we can count all products in the answer\n```
['C++']