Problem

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, memory1crash, memory2crash], wherecrashTime is the time (in seconds) when the program crashed andmemory1crash andmemory2crash are the available bits of memory in the first and second sticks respectively.

Examples

Example 1

1
2
3
4
5
6

Input: memory1 = 2, memory2 = 2
Output: [3,1,0]
Explanation: The memory is allocated as follows:
- At the 1st second, 1 bit of memory is allocated to stick 1. The first stick now has 1 bit of available memory.
- At the 2nd second, 2 bits of memory are allocated to stick 2. The second stick now has 0 bits of available memory.
- At the 3rd second, the program crashes. The sticks have 1 and 0 bits available respectively.

Example 2

1
2
3
4
5
6
7
8
9

Input: memory1 = 8, memory2 = 11
Output: [6,0,4]
Explanation: The memory is allocated as follows:
- At the 1st second, 1 bit of memory is allocated to stick 2. The second stick now has 10 bit of available memory.
- At the 2nd second, 2 bits of memory are allocated to stick 2. The second stick now has 8 bits of available memory.
- At the 3rd second, 3 bits of memory are allocated to stick 1. The first stick now has 5 bits of available memory.
- At the 4th second, 4 bits of memory are allocated to stick 2. The second stick now has 4 bits of available memory.
- At the 5th second, 5 bits of memory are allocated to stick 1. The first stick now has 0 bits of available memory.
- At the 6th second, the program crashes. The sticks have 0 and 4 bits available respectively.

Constraints

  • 0 <= memory1, memory2 <= 2^31 - 1

Solution

Method 1 – Simulation (Greedy Allocation)

Intuition

At each second, allocate memory to the stick with more available memory (or the first if equal). We simulate the process, incrementing the allocation each second, until neither stick can accommodate the next allocation.

Approach

  1. Initialize t = 1 (current second).
  2. While either stick has at least t bits available:
    • If memory1 >= memory2, allocate t bits from memory1 if possible, else from memory2.
    • Subtract t from the chosen stick.
    • Increment t.
  3. When neither stick can accommodate t bits, return [t, memory1, memory2].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

vector<int> memLeak(int memory1, int memory2) {
    int t = 1;
    while (memory1 >= t || memory2 >= t) {
        if (memory1 >= memory2) {
            if (memory1 >= t) memory1 -= t;
            else memory2 -= t;
        } else {
            if (memory2 >= t) memory2 -= t;
            else memory1 -= t;
        }
        ++t;
    }
    return {t, memory1, memory2};
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func memLeak(memory1, memory2 int) []int {
    t := 1
    for memory1 >= t || memory2 >= t {
        if memory1 >= memory2 {
            if memory1 >= t {
                memory1 -= t
            } else {
                memory2 -= t
            }
        } else {
            if memory2 >= t {
                memory2 -= t
            } else {
                memory1 -= t
            }
        }
        t++
    }
    return []int{t, memory1, memory2}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int[] memLeak(int memory1, int memory2) {
        int t = 1;
        while (memory1 >= t || memory2 >= t) {
            if (memory1 >= memory2) {
                if (memory1 >= t) memory1 -= t;
                else memory2 -= t;
            } else {
                if (memory2 >= t) memory2 -= t;
                else memory1 -= t;
            }
            t++;
        }
        return new int[]{t, memory1, memory2};
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun memLeak(memory1: Int, memory2: Int): IntArray {
        var m1 = memory1
        var m2 = memory2
        var t = 1
        while (m1 >= t || m2 >= t) {
            if (m1 >= m2) {
                if (m1 >= t) m1 -= t else m2 -= t
            } else {
                if (m2 >= t) m2 -= t else m1 -= t
            }
            t++
        }
        return intArrayOf(t, m1, m2)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def mem_leak(memory1: int, memory2: int) -> list[int]:
    t = 1
    m1, m2 = memory1, memory2
    while m1 >= t or m2 >= t:
        if m1 >= m2:
            if m1 >= t:
                m1 -= t
            else:
                m2 -= t
        else:
            if m2 >= t:
                m2 -= t
            else:
                m1 -= t
        t += 1
    return [t, m1, m2]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

fn mem_leak(mut memory1: i32, mut memory2: i32) -> Vec<i32> {
    let mut t = 1;
    while memory1 >= t || memory2 >= t {
        if memory1 >= memory2 {
            if memory1 >= t {
                memory1 -= t;
            } else {
                memory2 -= t;
            }
        } else {
            if memory2 >= t {
                memory2 -= t;
            } else {
                memory1 -= t;
            }
        }
        t += 1;
    }
    vec![t, memory1, memory2]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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

Complexity

  • ⏰ Time complexity: O(√(memory1 + memory2)) — Each allocation increases by 1, so the number of steps is about the square root of the total memory.
  • 🧺 Space complexity: O(1) — Only a few variables are used.