[C++] Binary search using std::partition_point and std::reverse_iterator without copying
The problem has "BinarySearch" tag, so it can be solved with std::partition_point, just like any other binary search problem. A small than minimal implementatio
The problem has "BinarySearch" tag, so it can be solved with `std::partition_point`, just like any other binary search problem. A small than minimal implementation of `counting_iterator` is presented such that it compiles with gcc 9, but I guess something from ranges could be used with later standard. To eliminate `nums` copying, `std::reverse_iterator` and templated function for product counting are employed. \n\nFor each `m`, there\'s a fixed number of pairs from (cartesian) product of nums1 and nums2 whose product is less than `m`, so we binary search for `m=k`. For more detailed explanation, see this explanation by @votrubac that I used: https://leetcode.com/problems/kth-smallest-product-of-two-sorted-arrays/discuss/1527753/Binary-Search-and-Two-Pointers .\n\n```\n#include <algorithm>\n\nstruct counting_iterator\n{\n    using value_type = long long;\n    using reference = long long;\n    using difference_type = long long;\n    using iterator_category = std::random_access_iterator_tag;\n    using pointer = void;\n\n    long long n_;\n\n    counting_iterator& operator++() { ++n_; return *this; }\n    counting_iterator& operator--() { --n_; return *this; }\n    void operator+=(long long d) { n_ += d; }\n    friend long long operator-(const counting_iterator& lhs, const counting_iterator &rhs) { return lhs.n_ - rhs.n_; }\n    long long operator*() const { return n_; }\n};\n\nclass Solution {\npublic:\n    long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, long long k) {\n\n        auto mid1 = std::lower_bound(nums1.begin(), nums1.end(), 0);\n        auto mid2 = std::lower_bound(nums2.begin(), nums2.end(), 0);\n\n        auto neg1 = std::make_pair(nums1.begin(), mid1), pos1 = std::make_pair(mid1, nums1.end());\n        auto neg2 = std::make_pair(nums2.begin(), mid2), pos2 = std::make_pair(mid2, nums2.end());\n\n        auto neg1_r = std::make_pair(std::make_reverse_iterator(mid1), std::make_reverse_iterator(nums1.begin()))\n            , pos1_r = std::make_pair(std::make_reverse_iterator(nums1.end()), std::make_reverse_iterator(mid1));\n        auto neg2_r = std::make_pair(std::make_reverse_iterator(mid2), std::make_reverse_iterator(nums2.begin()))\n            , pos2_r = std::make_pair(std::make_reverse_iterator(nums2.end()), std::make_reverse_iterator(mid2));\n\n        auto local_count_of_prods_less_than = [](auto range_pair1, auto range_pair2, long long m)->long long {\n            if (range_pair2.first == range_pair2.second)\n                return 0;\n\n            long long cnt = 0;\n\n            auto it2 = std::prev(range_pair2.second);\n\n            for (auto it1 = range_pair1.first; it1 != range_pair1.second; ++it1)\n            {\n                while ((long long)*it1 * *it2 > m)\n                {\n                    if (it2 == range_pair2.first)\n                        return cnt;\n                    else\n                        --it2;\n                }\n                cnt += std::distance(range_pair2.first, it2) + 1;\n            }\n            return cnt;\n        };\n\n        auto pos1_size = std::distance(pos1.first, pos1.second);\n        auto pos2_size = std::distance(pos2.first, pos2.second);\n        auto neg1_size = std::distance(neg1.first, neg1.second);\n        auto neg2_size = std::distance(neg2.first, neg2.second);\n\n\n        auto count_of_prods_less_than = [&](auto m)->long long\n        {\n            if (m >= 0)\n                return local_count_of_prods_less_than(pos1, pos2, m)\n                    + local_count_of_prods_less_than(neg1_r, neg2_r, m)\n                    + pos1_size * neg2_size + pos2_size * neg1_size;\n            else\n                return local_count_of_prods_less_than(neg1, pos2_r, m)\n                    + local_count_of_prods_less_than(neg2, pos1_r, m);\n        };\n\n        constexpr auto min_m = -100000LL*100000;\n        constexpr auto max_m = 100000LL*100000;\n\n        auto it = std::partition_point(\n            counting_iterator{ min_m }, counting_iterator{ max_m+1 }\n            , [&,k](auto m_cand) {\n                return count_of_prods_less_than(m_cand) < k; \n            });\n\n        return *it;\n    }\n};\n\n```
[]