Incremental Memory Leak

medium math simulation

Problem

You have two memory sticks with memory1 and memory2 bits available. A faulty program runs in seconds counted from 1. On the second numbered i, the program tries to allocate exactly i bits of memory.

The allocation always goes to whichever stick currently has more bits available; if both sticks have the same amount, it goes to the first stick. The program crashes at the first second i where i bits cannot be allocated to either stick (both sticks have fewer than i bits free).

Return an array [crashTime, memory1, memory2]: the second on which it crashed, and the bits still available in each stick at that moment.

Inputmemory1 = 2, memory2 = 2

Output[3, 1, 0]

Second 1: tie, allocate 1 to stick 1 → (1, 2). Second 2: stick 2 is larger, allocate 2 → (1, 0). Second 3: both have fewer than 3 bits, so it crashes. Answer is [3, 1, 0].

memory1

memory2

def mem_leak_crash(memory1, memory2):
    i = 1
    while i <= memory1 or i <= memory2:
        if memory1 >= memory2:
            memory1 -= i
        else:
            memory2 -= i
        i += 1
    return [i, memory1, memory2]

function memLeak(memory1, memory2) {
  let i = 1;
  while (i <= memory1 || i <= memory2) {
    if (memory1 >= memory2) {
      memory1 -= i;
    } else {
      memory2 -= i;
    }
    i += 1;
  }
  return [i, memory1, memory2];
}

class Solution {
    public int[] memLeak(int memory1, int memory2) {
        int i = 1;
        while (i <= memory1 || i <= memory2) {
            if (memory1 >= memory2) {
                memory1 -= i;
            } else {
                memory2 -= i;
            }
            i += 1;
        }
        return new int[]{ i, memory1, memory2 };
    }
}

vector<int> memLeak(int memory1, int memory2) {
    int i = 1;
    while (i <= memory1 || i <= memory2) {
        if (memory1 >= memory2) {
            memory1 -= i;
        } else {
            memory2 -= i;
        }
        i += 1;
    }
    return { i, memory1, memory2 };
}

Explanation

This is a greedy simulation. The rule is fixed and leaves no room for choice: on second i the i bits must go to the stick with more free memory, and ties break toward the first stick. So we just play it out second by second.

We keep a clock i starting at 1. The program keeps running as long as at least one stick can still hold the next request — that is, while i ≤ memory1 or i ≤ memory2. The moment both sticks have fewer than i bits, no allocation is possible and the program crashes on that very second.

Inside the loop we compare the two sticks. If memory1 ≥ memory2 (this covers the tie case too, since ≥ favours the first stick), we subtract i from memory1; otherwise we subtract i from memory2. Then we advance the clock with i += 1.

When the loop finally exits, i already holds the crash second (we incremented it after the last successful allocation, so it points at the request that failed), and memory1 and memory2 hold the leftover bits. We return [i, memory1, memory2].

Tracing the default example memory1 = 2, memory2 = 2: second 1 is a tie so stick 1 takes it → (1, 2); second 2 sees stick 2 larger → (1, 0); second 3 needs 3 bits but both sticks hold fewer, so it crashes. The answer is [3, 1, 0].

How fast is this? Each second removes i bits from the larger pile, and the total memory consumed after k seconds is 1 + 2 + … + k = k(k+1)/2. To exhaust roughly memory1 + memory2 bits we need k on the order of √(memory1 + memory2) steps, so the loop runs about that many times using only a couple of variables.

Time: O(√(memory1 + memory2)) Space: O(1)