Minimum Number of Operations to Make X and Y Equal

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

Understanding the Visualization

Input

x = 26, y = 1, find minimum operations

Process

Choose optimal sequence: ÷5, ÷5

Output

Minimum operations = 2

Key Takeaway

🎯 Key Insight: Division operations can make large jumps, so explore all possibilities with memoization for optimal efficiency

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

Approach	Time	Space	Notes
✓ Breadth-First Search	O(x)	O(x)	Level-by-level exploration to find shortest path
Memoized DFS	O(x)	O(x)	Top-down recursion with caching to avoid recalculating same states
Recursive DFS (Without Memoization)	O(4^n)	O(n)	Pure recursive exploration of all possible operation sequences

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 x - y;
    
    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.val > y) {
            return current.ops + current.val - y;
        }
        
        // Try all operations
        int nextVals[4];
        int count = 0;
        
        nextVals[count++] = current.val + 1;
        if (current.val > 1) {
            nextVals[count++] = current.val - 1;
        }
        if (current.val % 11 == 0) {
            nextVals[count++] = current.val / 11;
        }
        if (current.val % 5 == 0) {
            nextVals[count++] = current.val / 5;
        }
        
        for (int i = 0; i < count; i++) {
            int nextVal = nextVals[i];
            if (nextVal > 0 && nextVal < MAX_SIZE && !visited[nextVal]) {
                visited[nextVal] = true;
                queue[rear++] = (State){nextVal, current.ops + 1};
            }
        }
    }
    
    return -1; // Should never reach here
}

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Breadth-First Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler