Paste: 111

Author: 1111
Mode: python
Date: Thu, 6 Oct 2022 01:43:30
Plain Text |
class Solution:

     # O(1) intersection of two lines!!!
    def trade_math(self, comicBooks, coins, coinsNeeded, coinsOffered) -> int:
        def f(sales):
            return comicBooks - sales
        def g(sales):
            return (coins + coinsOffered * sales) / coinsNeeded
        m1 = -1
        b1 = comicBooks

        m2 = coinsOffered / coinsNeeded
        b2 = coins / coinsNeeded

        x = (b2 - b1) / (m1 - m2)
        return min(comicBooks, floor(f(x)), floor(g(x)))

    def trade_bsearch(self, comicBooks, coins, coinsNeeded, coinsOffered) -> int:

        # helper function
        def count(comicBooks, coins, coinsNeeded, coinsOffered, sales) -> int:
            # sell comic books
            comicBooks -= sales
            # get coinsOffered coins for each sold comic book
            coins += coinsOffered * sales

            # buy as many fiction books as possible.
            # you will either be limited:
            # 1. by the number of comic books you have, or
            # 2. the amount of coins you have
            fictionBooks = min(comicBooks, coins // coinsNeeded)
            return fictionBooks

        # O(log(n))
        lo = 0
        hi = comicBooks + 1
        while lo < hi:
            mid = lo + (hi - lo) // 2
            m = count(comicBooks, coins, coinsNeeded, coinsOffered, mid)
            right = mid
            rc = m
            while right < comicBooks and rc == m:
                rc = count(comicBooks, coins, coinsNeeded, coinsOffered, right)
                right += 1
            if right == comicBooks or rc < m:
                hi = mid
            else:
                lo = mid+1

        return count(comicBooks, coins, coinsNeeded, coinsOffered, lo)

    # Times out
    def trade(self, comicBooks, coins, coinsNeeded, coinsOffered) -> int:

        # helper function
        def count(comicBooks, coins, coinsNeeded, coinsOffered, sales) -> int:
            # sell comic books
            comicBooks -= sales
            # get coinsOffered coins for each sold comic book
            coins += coinsOffered * sales

            # buy as many fiction books as possible.
            # you will either be limited:
            # 1. by the number of comic books you have, or
            # 2. the amount of coins you have
            fictionBooks = min(comicBooks, coins // coinsNeeded)
            return fictionBooks
        
        best = 0
        for n in range(comicBooks+1):
            best = max(best, count(comicBooks, coins, coinsNeeded, coinsOffered, n))
        return best

New Annotation

Summary:
Author:
Mode:
Body: