Ruby memoization & bsearch solution, explained (100%/100%)
Intuition\nIf you know how many numbers you\'re going to reset, you can check the total from resetting them in optimal order in O(n^2) time with memoization.  U
# Intuition\nIf you know how many numbers you\'re going to reset, you can check the total from resetting them in optimal order in O(n^2) time with memoization.  Use a binary search to figure out how many numbers to reset.\n\n# Approach\n1. Special cases: if the sum is already low enough return 0; if all numbers must be reset because x and everything in nums2 is 0, return nums1.length.\n2. Create class variables for length and both arrays.\n3. Create a variable for the indices ordering nums2 by value.  (If we know we\'re resetting two things that have a different nums2 value, we want to reset the lower one first, since it will increase less.)\n4. More special cases: check if resetting one or no values would work.  (This speeds up the code.)\n5. Do a binary search for the numbers from 2 to length (exclusive), and find the lowest that returns a total less than k.\n6. Return the result, or else @len, since we know resetting @len works from the special cases we tested earlier.\n\nHelper function total (find the minimum total from resetting k values):\n1. Create a memo object.\n2. Create a sums array that calculates the value at each index if it\'s *not* reset.  (We calculate this multiple times in the next helper function, so this speeds it up.)\n3. Call the other helper function, starting at index 0 and k values to reset.\n\nHelper function change:\nThis iterates throuh the values (in the order of @order) and tries changing k of them.  Use memoization to efficiently find the lowest possible total.\n1. If you have negative changes, this situation isn\'t possible.  Return infinity so this option is never selected.\n2. Return 0 if you\'ve reached the end of the array.\n3. Return the value stored in memo if it exists.\nTwo options at each index:\n    1. Do not change the value at that index -- increment i and add @sum[i]\n    2. Change that index: decrement changes and multiply by the nums2 value.  (Right now it\'s 0, but you\'re going to add @nums2[i] (changes-1) times.)\n4. Take the option with the lowest value, memoize, and return. \n\n# Complexity\n- Time complexity:\n$$O(n^2 * log(n))$$\n\n- Space complexity:\n$$O(n^2)$$\n\n# Code\n```\ndef minimum_time(nums1, nums2, x) # O(n^2 * log(n)) -> (10**3)**2 * 10**1 -> 10**7\n    return 0 if nums1.sum <= x\n    return nums1.count { |n| n > 0 } if x == 0 && nums2.all? { |k| k == 0 }\n\n    @len = nums1.length\n    @nums1, @nums2 = nums1, nums2\n    \n    @order = (0...@len).to_a.sort_by { |i| nums2[i] }\n\n    return 1 if total(1) <= x\n    return -1 unless total(@len) <= x\n        \n    res = (2...@len).bsearch do |k|\n        total(k) <= x\n    end\n    \n    res || @len\nend\n\ndef total(k)\n    @memo = Array.new(@len) { Array.new(k) }\n    @sum = (0...@len).to_a.map { |i| @nums1[@order[i]] + k * @nums2[@order[i]] }\n    change(0,k)\nend\n\ndef change(i,changes)\n    return Float::INFINITY if changes < 0\n    return 0 if i == @len\n    return @memo[i][changes] if @memo[i][changes]\n    \n    idx = @order[i]\n    \n    option1 = change(i+1, changes) + @sum[i]\n    option2 = change(i+1, changes-1) + (changes-1) * @nums2[idx]\n    \n    @memo[i][changes] = [option1,option2].min\nend\n```
['Ruby']