Algorithm help :Given a num, can it finally be 1

Question

Given a number, you can divide it or its contiguous part by 2 , or multiply it or its continuous part by 2. Can the number finally be 1?

For example : 13

3 is a part of 13, first we take 3 * 2 = 6, the num turn to be 16,
second we can operate the whole num 16, 16 / 2 = 8, the num is 8 now,
8/2 = 4, num is 4 now,
4/2 = 2, num is 2 now,
2/2 = 1, num is 1 now.

finally we can say 13 can turn into 1, and the path is 13->16->8->4->2->1, we can use a List to store the path.

Example ：27

first we operate the whole num 27, 27 * 2 = 54；
then we take 4 as the part of 54, 4 / 2 = 2 , so the 4 is 2 now, num becomes 52;
operate 52, 52 / 2 = 26, num is 26 now；
operate 26, 26 / 2 = 13, num is 13 now；

we just analyzed 13, so 27 can turn into 1 finally.
 

How to analyze such problem? What's the main idea of solving such type problem?

---

Sorry about the confusing description, let's take a more complex example: 316

16 is a contiguous part, let 16 / 2 = 8 , so the num is 38 now,

then take 8 / 2 = 4 , the num is 34,

take 4 / 2 = 2, the num is 32,

now take the whole num 32 / 2 = 16,

16 / 2 = 8， num is 8,

8 / 2 = 4, num is 4,

4 / 2 = 2, num is 2,

finally 2 / 2 = 1.

We say, original num 316 can turn into 1 finally after above conversion.

And the contiguous part means, if the input num is 12345,

then 123, 234,345,12,2345 and so on, they are all contiguous parts.

Any continuous subset of num is fine，including head or tail is NOT necessary.

---

The question is :

1. How to judge such a num? And if the num can turn into 1, print the path.
2. Can you find the shortest way?

---

I got some hints from interviewer (The interview is over):

1. Most of numbers are eligible, that means nums which are NOT eligible, these characteristics are obvious.

2. Brute fore way's time complexity is too high, we should pruning timely. (Slide window + pruning ?)

question from:https://stackoverflow.com/questions/65919220/algorithm-help-given-a-num-can-it-finally-be-1

Answer 1

Here is a simple and unoptimized breadth-first search.

def shortest_digit_path (n):
    path_from = {n: None}
    queue = [n]
    count = 0
    while True:
        m = queue.pop(0)
        count += 1
        if 0 == count %1000:
            print((count, m))

        if m == 1:
            break
        x = str(m)
        for i in range(len(x)):
            for j in range(i+1, len(x) + 1):
                y = x[0:i]
                z = x[i:j]
                w = x[j:]

                if z[0] == '0':
                    continue # The continuous section is not a proper number.

                # Try half of z
                if z[-1] in ['2', '4', '6', '8']:
                    next_m = int(y + str(int(z)//2) + w)
                    if next_m not in path_from:
                        path_from[next_m] = m
                        queue.append(next_m)

                # Try doubling z
                next_m = int(y + str(int(z)*2) + w)
                if next_m not in path_from:
                    path_from[next_m] = m
                    queue.append(next_m)

    path = []
    while m is not None:
        path.append(m)
        m = path_from[m]
    return list(reversed(path))

After playing around with this for a bit, I came up with the following observations.

1. If the number ends in 0 or 5, there is no path to having any other digit at the end, and therefore you can't get to 1. (The above function will just run forever.
2. For anything else we can find a path just dealing with 1-2 digits at a time.

Here are the special cases for observation #2. Our first goal is to get to just 0, 1, and 5 as digits.

0: 0
1: 1
2: 2 -> 1
3: 3 -> 6 -> 12 -> 24 -> 28 -> 56 -> 112 -> 16 -> 8 -> 4 -> 2 -> 1
4: 4 -> 2 -> 1
5: 5
6: 6 -> 12 -> 24 -> 28 -> 56 -> 112 -> 16 -> 8 -> 4 -> 2 -> 1
7: 7 -> 14 -> 28 -> 56 -> 112 -> 16 -> 8 -> 4 -> 2 -> 1
8: 8 -> 4 -> 2 -> 1
9: 9 -> 18 -> 28 -> 56 -> 112 -> 16 -> 8 -> 4 -> 2 -> 1

And now from the start of the number we have to deal with the following cases that reduce the number of digits and get back to our desired form.

10: 10 -> 5
11: 11 -> 22 -> 24 -> 28 -> 56 -> 112 -> 16 -> 8 -> 4 -> 2 -> 1
15: 15 -> 110 -> 220 -> 240 -> 280 -> 560 -> 1120 -> 160 -> 80 -> 40 -> 20 -> 10 -> 5
50: 50 -> 25 -> 15 -> 110 -> 220 -> 240 -> 280 -> 560 -> 1120 -> 160 -> 80 -> 40 -> 20 -> 10 -> 5
51: 51 -> 52 -> 26 -> 16 -> 8 -> 4 -> 2 -> 1
55: 55 -> 510 -> 520 -> 260 -> 160 -> 80 -> 40 -> 20 -> 10 -> 5

With this set of rules we can first normalize the number to a standard form, then we can shorten it one digit at a time. This lets us essentially instantly come up with a path. Almost certainly not the shortest one, but definitely a path.

Writing that function is left as an exercise to the reader.

Now back to the shortest path. The algorithm for the breadth-first search can be made much faster if we start with a breadth-first search from both ends and meet in the middle. For this you'd need to also have a path_to that is initialized with {1: None}, a queue containing elements of the form (m, is_rising) and initialize it with [(1, True), (n: False)]. You'd then have to branch on is_rising and before entering values into path_from/path_to check for whether it is in path_to/path_from. If it is, you've met in the middle. Now work out both halves of the path and join them together.

The approach is tricker. But it will let you find the shortest path in the square root of the number of steps that the current approach takes.