Problem

You are given two positive integers x and y.

In one operation, you can do one of the four following operations:

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

Return _theminimum number of operations required to make _ x and y equal.

Examples

Example 1

1
2
3
4
5
6
7

Input: x = 26, y = 1
Output: 3
Explanation: We can make 26 equal to 1 by applying the following operations: 
1. Decrement x by 1
2. Divide x by 5
3. Divide x by 5
It can be shown that 3 is the minimum number of operations required to make 26 equal to 1.

Example 2

1
2
3
4
5
6
7
8

Input: x = 54, y = 2
Output: 4
Explanation: We can make 54 equal to 2 by applying the following operations: 
1. Increment x by 1
2. Divide x by 11 
3. Divide x by 5
4. Increment x by 1
It can be shown that 4 is the minimum number of operations required to make 54 equal to 2.

Example 3

1
2
3
4
5
6
7
8
9

Input: x = 25, y = 30
Output: 5
Explanation: We can make 25 equal to 30 by applying the following operations: 
1. Increment x by 1
2. Increment x by 1
3. Increment x by 1
4. Increment x by 1
5. Increment x by 1
It can be shown that 5 is the minimum number of operations required to make 25 equal to 30.

Constraints

  • 1 <= x, y <= 10^4

Solution

Method 1 – BFS / DP with Memoization

Intuition

We want the minimum steps to reach y from x using allowed operations. BFS or DP with memoization works well since the state space is small (<= 10^4).

Approach

  1. Use BFS from x, each state is a value and its step count.
  2. For each value, try all possible operations: divide by 11, divide by 5, increment, decrement.
  3. Stop when reaching y, return the step count.
  4. Alternatively, use DP with memoization to avoid recomputation.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <queue>
#include <unordered_set>
using namespace std;
class Solution {
public:
    int minimumOperations(int x, int y) {
        queue<pair<int, int>> q;
        unordered_set<int> vis;
        q.push({x, 0});
        vis.insert(x);
        while (!q.empty()) {
            auto [v, steps] = q.front(); q.pop();
            if (v == y) return steps;
            for (int nv : {v - 1, v + 1}) {
                if (nv >= 1 && nv <= 10000 && !vis.count(nv)) {
                    q.push({nv, steps + 1}); vis.insert(nv);
                }
            }
            if (v % 5 == 0 && v / 5 >= 1 && !vis.count(v / 5)) {
                q.push({v / 5, steps + 1}); vis.insert(v / 5);
            }
            if (v % 11 == 0 && v / 11 >= 1 && !vis.count(v / 11)) {
                q.push({v / 11, steps + 1}); vis.insert(v / 11);
            }
        }
        return -1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

func minimumOperations(x, y int) int {
    type pair struct{ v, steps int }
    vis := make(map[int]struct{})
    q := []pair{{x, 0}}
    vis[x] = struct{}{}
    for len(q) > 0 {
        p := q[0]; q = q[1:]
        if p.v == y { return p.steps }
        for _, nv := range []int{p.v - 1, p.v + 1} {
            if nv >= 1 && nv <= 10000 {
                if _, ok := vis[nv]; !ok {
                    q = append(q, pair{nv, p.steps + 1}); vis[nv] = struct{}{}
                }
            }
        }
        if p.v%5 == 0 && p.v/5 >= 1 {
            if _, ok := vis[p.v/5]; !ok {
                q = append(q, pair{p.v/5, p.steps + 1}); vis[p.v/5] = struct{}{}
            }
        }
        if p.v%11 == 0 && p.v/11 >= 1 {
            if _, ok := vis[p.v/11]; !ok {
                q = append(q, pair{p.v/11, p.steps + 1}); vis[p.v/11] = struct{}{}
            }
        }
    }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

import java.util.*;
class Solution {
    public int minimumOperations(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        Set<Integer> vis = new HashSet<>();
        q.add(new int[]{x, 0});
        vis.add(x);
        while (!q.isEmpty()) {
            int[] p = q.poll();
            int v = p[0], steps = p[1];
            if (v == y) return steps;
            for (int nv : new int[]{v - 1, v + 1}) {
                if (nv >= 1 && nv <= 10000 && !vis.contains(nv)) {
                    q.add(new int[]{nv, steps + 1}); vis.add(nv);
                }
            }
            if (v % 5 == 0 && v / 5 >= 1 && !vis.contains(v / 5)) {
                q.add(new int[]{v / 5, steps + 1}); vis.add(v / 5);
            }
            if (v % 11 == 0 && v / 11 >= 1 && !vis.contains(v / 11)) {
                q.add(new int[]{v / 11, steps + 1}); vis.add(v / 11);
            }
        }
        return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    fun minimumOperations(x: Int, y: Int): Int {
        val vis = mutableSetOf<Int>()
        val q = ArrayDeque<Pair<Int, Int>>()
        q.add(x to 0); vis.add(x)
        while (q.isNotEmpty()) {
            val (v, steps) = q.removeFirst()
            if (v == y) return steps
            for (nv in listOf(v - 1, v + 1)) {
                if (nv in 1..10000 && nv !in vis) {
                    q.add(nv to steps + 1); vis.add(nv)
                }
            }
            if (v % 5 == 0 && v / 5 >= 1 && v / 5 !in vis) {
                q.add(v / 5 to steps + 1); vis.add(v / 5)
            }
            if (v % 11 == 0 && v / 11 >= 1 && v / 11 !in vis) {
                q.add(v / 11 to steps + 1); vis.add(v / 11)
            }
        }
        return -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

from collections import deque
class Solution:
    def minimumOperations(self, x: int, y: int) -> int:
        vis = set([x])
        q = deque([(x, 0)])
        while q:
            v, steps = q.popleft()
            if v == y:
                return steps
            for nv in (v - 1, v + 1):
                if 1 <= nv <= 10000 and nv not in vis:
                    q.append((nv, steps + 1)); vis.add(nv)
            if v % 5 == 0 and v // 5 >= 1 and v // 5 not in vis:
                q.append((v // 5, steps + 1)); vis.add(v // 5)
            if v % 11 == 0 and v // 11 >= 1 and v // 11 not in vis:
                q.append((v // 11, steps + 1)); vis.add(v // 11)
        return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

use std::collections::{HashSet, VecDeque};
impl Solution {
    pub fn minimum_operations(x: i32, y: i32) -> i32 {
        let mut vis = HashSet::new();
        let mut q = VecDeque::new();
        vis.insert(x);
        q.push_back((x, 0));
        while let Some((v, steps)) = q.pop_front() {
            if v == y { return steps; }
            for nv in [v - 1, v + 1] {
                if nv >= 1 && nv <= 10000 && !vis.contains(&nv) {
                    q.push_back((nv, steps + 1)); vis.insert(nv);
                }
            }
            if v % 5 == 0 && v / 5 >= 1 && !vis.contains(&(v / 5)) {
                q.push_back((v / 5, steps + 1)); vis.insert(v / 5);
            }
            if v % 11 == 0 && v / 11 >= 1 && !vis.contains(&(v / 11)) {
                q.push_back((v / 11, steps + 1)); vis.insert(v / 11);
            }
        }
        -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    minimumOperations(x: number, y: number): number {
        const vis = new Set<number>([x]);
        const q: [number, number][] = [[x, 0]];
        let head = 0;
        while (head < q.length) {
            const [v, steps] = q[head++];
            if (v === y) return steps;
            for (const nv of [v - 1, v + 1]) {
                if (nv >= 1 && nv <= 10000 && !vis.has(nv)) {
                    q.push([nv, steps + 1]); vis.add(nv);
                }
            }
            if (v % 5 === 0 && v / 5 >= 1 && !vis.has(v / 5)) {
                q.push([v / 5, steps + 1]); vis.add(v / 5);
            }
            if (v % 11 === 0 && v / 11 >= 1 && !vis.has(v / 11)) {
                q.push([v / 11, steps + 1]); vis.add(v / 11);
            }
        }
        return -1;
    }
}

Complexity

  • ⏰ Time complexity: O(N) — N = 10^4, each value visited at most once.
  • 🧺 Space complexity: O(N) — for visited set and queue.