Problem Description
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 amount of memory every second. At the ith second (starting from 1), i bits of memory are allocated to the stick with more available memory (or from the first memory stick if both have the same available memory). If neither stick has at least i bits of available memory, the program crashes. Return an array containing [crashTime, memory1_crash, memory2_crash], where crashTime is the time (in seconds) when the program crashed and memory1_crash and memory2_crash are the available bits of memory in the first and second sticks respectively.
Key Insights
- Memory allocation occurs every second with the amount equal to the second number.
- The memory is allocated to the stick with more available memory or to the first stick in case of a tie.
- The program crashes when neither stick can accommodate the required memory for that second.
- The solution involves simulating the memory allocation process second by second until a crash occurs.
Space and Time Complexity
Time Complexity: O(n), where n is the time until the program crashes. Space Complexity: O(1), since we only use a constant amount of extra space for variables.
Solution
The solution involves simulating the memory allocation process. We initialize two variables for memory sticks and a time counter. In each iteration, we check which stick has more memory and allocate the required bits for that second. We keep track of the time and memory left in each stick. The process continues until neither stick can allocate the required bits, at which point we return the crash time and the remaining memory in both sticks.