{"id":8459,"date":"2021-06-01T07:56:15","date_gmt":"2021-06-01T14:56:15","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8459"},"modified":"2021-06-01T07:57:03","modified_gmt":"2021-06-01T14:57:03","slug":"leetcode-1860-incremental-memory-leak","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/simulation\/leetcode-1860-incremental-memory-leak\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1860. Incremental Memory Leak"},"content":{"rendered":"\n

You are given two integers memory1<\/code> and memory2<\/code> representing the available memory in bits on two memory sticks. There is currently a faulty program running that consumes an increasing amount of memory every second.<\/p>\n\n\n\n

At the ith<\/sup><\/code> second (starting from 1), i<\/code> bits of memory are allocated to the stick with more available memory<\/strong> (or from the first memory stick if both have the same available memory). If neither stick has at least i<\/code> bits of available memory, the program crashes<\/strong>.<\/p>\n\n\n\n

Return an array containing <\/em>[crashTime, memory1crash<\/sub>, memory2crash<\/sub>]<\/code>, where <\/em>crashTime<\/code> is the time (in seconds) when the program crashed and <\/em>memory1crash<\/sub><\/code> and <\/em>memory2crash<\/sub><\/code> are the available bits of memory in the first and second sticks respectively<\/em>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> memory1 = 2, memory2 = 2\nOutput:<\/strong> [3,1,0]\nExplanation:<\/strong> The memory is allocated as follows:\n- At the 1st<\/sup> second, 1 bit of memory is allocated to stick 1. The first stick now has 1 bit of available memory.\n- At the 2nd<\/sup> second, 2 bits of memory are allocated to stick 2. The second stick now has 0 bits of available memory.\n- At the 3rd<\/sup> second, the program crashes. The sticks have 1 and 0 bits available respectively.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> memory1 = 8, memory2 = 11\nOutput:<\/strong> [6,0,4]\nExplanation:<\/strong> The memory is allocated as follows:\n- At the 1st<\/sup> second, 1 bit of memory is allocated to stick 2. The second stick now has 10 bit of available memory.\n- At the 2nd<\/sup> second, 2 bits of memory are allocated to stick 2. The second stick now has 8 bits of available memory.\n- At the 3rd<\/sup> second, 3 bits of memory are allocated to stick 1. The first stick now has 5 bits of available memory.\n- At the 4th<\/sup> second, 4 bits of memory are allocated to stick 2. The second stick now has 4 bits of available memory.\n- At the 5th<\/sup> second, 5 bits of memory are allocated to stick 1. The first stick now has 0 bits of available memory.\n- At the 6th<\/sup> second, the program crashes. The sticks have 0 and 4 bits available respectively.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 0 <= memory1, memory2 <= 231<\/sup> - 1<\/code><\/li><\/ul>\n\n\n\n
    Solution: Simulation<\/strong><\/h2>\n\n\n\n
    Time complexity: O(max(memory1, memory2)0.5<\/sup>)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    Python3<\/h2>\n
    \n\n
    \nclass Solution:\n  def memLeak(self, memory1: int, memory2: int) -> List[int]:\n    for i in range(1, 2**30):\n      if max(memory1, memory2) < i:\n        return [i, memory1, memory2]\n      elif memory1 >= memory2:\n        memory1 -= i\n      else:\n        memory2 -= i\n    return None\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given two integers memory1 and memory2 representing the available memory in bits on two memory sticks. There is currently a faulty program running that consumes an increasing…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48],"tags":[177,179],"class_list":["post-8459","post","type-post","status-publish","format-standard","hentry","category-simulation","tag-medium","tag-simulation","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8459","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8459"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8459\/revisions"}],"predecessor-version":[{"id":8461,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8459\/revisions\/8461"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8459"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8459"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8459"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}