<p>You are given two <strong>0-indexed</strong> arrays <code>nums</code> and <code>cost</code> consisting each of <code>n</code> <strong>positive</strong> integers.</p>

<p>You can do the following operation <strong>any</strong> number of times:</p>

<ul>
	<li>Increase or decrease <strong>any</strong> element of the array <code>nums</code> by <code>1</code>.</li>
</ul>

<p>The cost of doing one operation on the <code>i<sup>th</sup></code> element is <code>cost[i]</code>.</p>

<p>Return <em>the <strong>minimum</strong> total cost such that all the elements of the array </em><code>nums</code><em> become <strong>equal</strong></em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,3,5,2], cost = [2,3,1,14]
<strong>Output:</strong> 8
<strong>Explanation:</strong> We can make all the elements equal to 2 in the following way:
- Increase the 0<sup>th</sup> element one time. The cost is 2.
- Decrease the 1<sup><span style="font-size: 10.8333px;">st</span></sup> element one time. The cost is 3.
- Decrease the 2<sup>nd</sup> element three times. The cost is 1 + 1 + 1 = 3.
The total cost is 2 + 3 + 3 = 8.
It can be shown that we cannot make the array equal with a smaller cost.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,2,2,2,2], cost = [4,2,8,1,3]
<strong>Output:</strong> 0
<strong>Explanation:</strong> All the elements are already equal, so no operations are needed.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == nums.length == cost.length</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i], cost[i] &lt;= 10<sup>6</sup></code></li>
	<li>Test cases are generated in a way that the output doesn&#39;t exceed&nbsp;2<sup>53</sup>-1</li>
</ul>

class Solution:
    def minCost(self, nums: List[int], cost: List[int]) -> int:
        # solution redone here, original solution further below
        # min_x sum_i |x - n_i| * c_i
        # this is continuous convex function of x
        # recall that it increases as you go away from the minimum
        # use this property to binary search for minimum
        left, right = min(nums), max(nums)
        while left < right - 1:
            mid = (left + right) // 2
            c1, c2, c3 = self.get_cost(mid - 1, nums, cost), self.get_cost(mid, nums, cost), self.get_cost(mid + 1, nums, cost)
            if c1 >= c2 and c2 <= c3:
                return c2
            elif c1 >= c2 >= c3:
                left = mid + 1
            # elif c1 <= c2 <= c3:
            else:
                right = mid - 1
        return min(self.get_cost(left, nums, cost), self.get_cost(right, nums, cost))
    
    def get_cost(self, x, nums, cost):
        res = 0
        for num, c in zip(nums, cost):
            res += abs(x - num) * c
        return res
















































    #     """
    #     In math, this problem is written as
    #     minimize_{k} sum_{i=0}^{n-1} abs(nums[i] - k) * cost[i],
    #     subject to the constraints that k is an integer and that
    #     min(nums) <= k <= max(nums).

    #     Note that cost is entrywise non-negative. Define the function
    #     f whose domain is real numbers, as
    #     f(k) = sum_{i=0}^{n-1} abs(nums[i] - k) * cost[i].
    #     Note that f is a continuous convex function of k.
    #     The interval [min(nums), max(nums)] is a compact set,
    #     so f achieves its minimum over this set. Let m be a
    #     minimizer, so that f(m) = min_{k in [min(nums), max(nums)]} f(k).
    #     We claim that m is also a global minimizer, so that
    #     f(m) = min_{k in reals} f(k). This follows simply from
    #     the fact that if we consider any x < min(nums), then
    #     f(x) > f(min(nums)) >= f(m), also that x > max(nums) implies
    #     f(x) > f(max(nums)) >= f(m).

    #     Now, note that f is non-strictly increasing as we move away from m.
    #     As a contradiction, assume f is decreasing over some
    #     interval as we move away from m. So there exists
    #     x < y < m by continuity such that f(x) < f(y), or x > y > m
    #     such that f(x) < f(y). Since both cases are symmetric, we
    #     consider the former. Note we could assume y < m due to
    #     continuity.

    #     Then note by the convexity of f, and the fact that
    #     y lies between x and m, that there exists t in [0,1]
    #     such that
    #     f(y) = f(t x + (1-t) m) <= t f(x) + (1-t) f(m)
    #     <= t f(x) + (1-t) f(x)
    #     = f(x)
    #     < f(y),
    #     where we used the fact that m is a minimizer of f.

    #     So we have arrived at a contradiction, and shown that
    #     f increases as we move away from the minimizer m. Indeed,
    #     we have shown this property true for any one dimensional
    #     continuous convex function.

    #     Now it should be intutive that we can minimize a continuous
    #     convex function, whose minimizer is known to lie in an
    #     interval, via binary search. The key is what condition to
    #     do binary search on. Via the fact we proved above, we know
    #     that if we are decreasing as we move right then we are to
    #     the left of m, and if we are increasing as we move right
    #     then we are to the right of m.

    #     So how do identify whether we are increasing or decreasing at
    #     a point? For a differentiable function, just take the derivative
    #     and see whether it is positive of negative!

    #     But our function f is not differentiable.

    #     However, notice that for the purposes of this problem,
    #     we only care about identifying the
    #     *integer* that minimizes f in the interval
    #     [min(nums), max(nums)]. So if we want to identify
    #     whether f is increasing or decreasing at a point x,
    #     just compare f(x) to f(x+1) and f(x-1). Then just binary search.

    #     I think you can actually show that m is an integer,
    #     but we don't need to do that.
    #     """
    #     n = len(nums)
    #     left, right = min(nums), max(nums)

    #     while left < right - 1:
    #         mid = (left + right) // 2
    #         a = self.evaluate(nums, cost, mid - 1)
    #         b = self.evaluate(nums, cost, mid)
    #         c = self.evaluate(nums, cost, mid + 1)

    #         if a <= b <= c:
    #             # increasing
    #             right = mid
    #         elif a >= b >= c:
    #             # decreasing
    #             left = mid
    #         else:
    #             # a >= b <= c
    #             # because b cannot be larger than max(a,c) due to convexity
    #             return b
    #     a = self.evaluate(nums, cost, left)
    #     b = self.evaluate(nums, cost, right)
    #     if a <= b:
    #         return a
    #     return b

    # def evaluate(self, nums, cost, k):
    #     # returns the cost if all integers in nums are moved to k
    #     n = len(nums)
    #     res = 0
    #     for i in range(n):
    #         res += cost[i] * abs(k - nums[i])
    #     return res
464