Minimum Number of Operations to Make X and Y Equal - Problem

You are given two positive integers x and y. In one operation, you can do one of the four following operations:

Divide x by 11 if x is a multiple of 11.
Divide x by 5 if x is a multiple of 5.
Decrement x by 1.
Increment x by 1.

Return the minimum number of operations required to make x and y equal.

Input & Output

Example 1 — Basic Division

$ Input: x = 26, y = 1

› Output: 2

💡 Note: 26 → 5 (divide by 5) → 1 (divide by 5). Total: 2 operations.

Example 2 — Already Equal

$ Input: x = 54, y = 54

› Output: 0

💡 Note: x and y are already equal, so no operations needed.

Example 3 — Increment Strategy

$ Input: x = 25, y = 30

› Output: 5

💡 Note: Since y > x, we can only increment: 25 → 26 → 27 → 28 → 29 → 30. Total: 5 operations.

Constraints

1 ≤ x, y ≤ 10⁴
Both x and y are positive integers

Visualization

Tap to expand

Asked in

G Google 23 a Amazon 18 f Meta 15

The key insight is that division operations can make large jumps, so sometimes it's optimal to increment x to make it divisible before dividing. Best approach is memoized DFS which caches results to avoid recalculating same states. Time: O(x), Space: O(x)

Common Approaches

✓ Breadth-First Search

⏱️ Time: O(x) Space: O(x)

Use BFS with queue to explore all possible states level by level. Each level represents one more operation, guaranteeing we find the minimum number of operations first.

Memoized DFS

⏱️ Time: O(x) Space: O(x)

Use recursive DFS with memoization to cache results of subproblems. When we encounter the same value again, we return the cached result instead of recalculating.

Recursive DFS (Without Memoization)

⏱️ Time: O(4^n) Space: O(n)

Try all four operations at each step recursively. For each current value, explore dividing by 11, dividing by 5, incrementing, and decrementing, taking the minimum operations needed.

Breadth-First Search — Algorithm Steps

Initialize queue with starting value x
For each level, try all 4 operations on current values
Use visited set to avoid cycles
Return operations when target y is reached

Visualization

Tap to expand

Step-by-Step Walkthrough

Level 0

Start with x = 26

Level 1

Explore: 27, 25, 5 (÷5 valid)

Level 2

From 5: try 6, 4, 1 (÷5 valid)

Code -

solution.c — C

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

#define MAX_SIZE 100000

typedef struct {
    int val;
    int ops;
} State;

int solution(int x, int y) {
    if (x == y) return 0;
    if (x < y) return y - x;
    
    State queue[MAX_SIZE];
    bool visited[MAX_SIZE] = {false};
    int front = 0, rear = 0;
    
    queue[rear++] = (State){x, 0};
    if (x < MAX_SIZE) visited[x] = true;
    
    while (front < rear) {
        State current = queue[front++];
        
        if (current.val == y) {
            return current.ops;
        }
        
        // If current < y, we can only increment
        if (current.val < y) {
            return current.ops + (y - current.val);
        }
        
        // Try all operations
        int nextVals[4];
        int count = 0;
        
        // Only explore reasonable bounds to avoid infinite search
        if (current.val + 1 <= 2 * y && current.val + 1 < MAX_SIZE && !visited[current.val + 1]) {
            nextVals[count++] = current.val + 1;
        }
        
        if (current.val > 1 && !visited[current.val - 1]) {
            nextVals[count++] = current.val - 1;
        }
        
        if (current.val % 11 == 0 && current.val / 11 < MAX_SIZE && !visited[current.val / 11]) {
            nextVals[count++] = current.val / 11;
        }
        
        if (current.val % 5 == 0 && current.val / 5 < MAX_SIZE && !visited[current.val / 5]) {
            nextVals[count++] = current.val / 5;
        }
        
        for (int i = 0; i < count; i++) {
            int nextVal = nextVals[i];
            if (nextVal > 0 && nextVal < MAX_SIZE) {
                visited[nextVal] = true;
                queue[rear++] = (State){nextVal, current.ops + 1};
            }
        }
    }
    
    return -1;
}

int main() {
    int x, y;
    scanf("%d %d", &x, &y);
    printf("%d\n", solution(x, y));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(x)

In worst case, we might visit all numbers from 1 to x once

✓ Linear Growth

Space Complexity

O(x)

Queue and visited set can contain up to x different states

✓ Linear Space

32.4K Views

Medium Frequency

~15 min Avg. Time

876 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

Minimum Number of Operations to Make X and Y Equal - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Breadth-First Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler