Incremental Memory Leak - Practice Coding Problems

Incremental Memory Leak - Problem

Math Simulation Medium

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

Input & Output

Example 1 — Basic Case

$ Input: memory1 = 2, memory2 = 2

› Output: [3,1,0]

💡 Note: Second 1: allocate 1 bit to memory1 (both equal, choose first) → [1,2]. Second 2: allocate 2 bits to memory2 (2 > 1) → [1,0]. Second 3: need 3 bits but memory1 has only 1, memory2 has 0 → crash at second 3 with remaining [1,0]

Example 2 — Unequal Memory

$ Input: memory1 = 8, memory2 = 11

› Output: [6,0,4]

💡 Note: Allocation sequence: [8,11] → [7,11] → [7,9] → [4,9] → [4,5] → [4,0] → crash at second 6 when need 6 bits but max available is 4

Example 3 — Single Large Memory

$ Input: memory1 = 1, memory2 = 8

› Output: [4,0,6]

💡 Note: Second 1: [0,8], Second 2: [0,6], Second 3: [0,3], Second 4 needs 4 bits but only 3 available → crash

Constraints

0 ≤ memory1, memory2 ≤ 2³¹ - 1

Visualization

Tap to expand

Understanding the Visualization

Initial Memory

Two memory sticks with given capacities

Progressive Allocation

Each second allocates more bits to the fuller stick

Crash Point

Program crashes when neither stick can handle required allocation

Key Takeaway

🎯 Key Insight: Always allocate to the memory stick with more available space, and track when allocation becomes impossible

Asked in

a Amazon 15 M Microsoft 12 G Google 8

The key insight is to simulate the memory allocation process second by second, always choosing the memory stick with more available memory. The simulation approach is straightforward and efficient for this problem. Time: O(√n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Simulation Approach	O(√n)	O(1)	Simulate each second until crash occurs
Mathematical Optimization	O(log n)	O(1)	Use arithmetic formulas to calculate when each stick runs out

Simulation Approach — Algorithm Steps

Initialize current time to 1
At each second, find stick with more memory
Allocate required bits to that stick
Check if next allocation is possible
Return crash time and remaining memory

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Both memory sticks start with given capacity

Allocation Process

Each second allocates increasing bits to fuller stick

Crash Detection

Program crashes when neither stick can handle allocation

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

void solution(int memory1, int memory2, int* result) {
    int time = 1;
    
    while (1) {
        // Choose stick with more memory (stick 1 if equal)
        if (memory1 >= memory2) {
            if (memory1 < time) {
                break;
            }
            memory1 -= time;
        } else {
            if (memory2 < time) {
                break;
            }
            memory2 -= time;
        }
        time++;
    }
    
    result[0] = time;
    result[1] = memory1;
    result[2] = memory2;
}

int main() {
    int memory1, memory2;
    scanf("%d", &memory1);
    scanf("%d", &memory2);
    
    int result[3];
    solution(memory1, memory2, result);
    
    printf("[%d,%d,%d]\n", result[0], result[1], result[2]);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(√n)

Loop runs until sum reaches total memory, which is roughly √(2×max(memory1,memory2))

✓ Linear Growth

Space Complexity

O(1)

Only uses constant extra variables for tracking current state

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

842 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Simulation Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler