[백준] 16953번: A -> B

https://www.acmicpc.net/problem/16953

initial

I tried finding out a pattern. Maybe it is a dp question that builds upon previous case? But When I started thinking of the solution from the back like from 162 to make it to 2, and we have 2 choices (to divide it by 2 or delete the 1 at the right side). If we cant do both choices, we return -1 because it is unreachable.

The edge case of returning -1 was a bit tricky. I had to add while m>n to the recursive loop of while m!=n and m>n to prevent it from going all the way for test case like 4 42. After we exit this recursion, if m<n then it is unreachable so return -1 else we return count.

solution

import sys
input = sys.stdin.readline

n,m=map(int,input().split())
count=1
while m!=n and m>n:
    if m%2==0:
        m//=2
        count+=1
    elif str(m)[-1]== str(1):
        m = int(str(m)[:-1])
        count+=1
    else:
        print(-1)
        exit()
if m<n:
    print(-1)
else:
    print(count)

bfs way (clever)

I think this is also good if you cant think of the maths way. Although this is less efficient, it is clever

from collections import deque
a,b = map(int,input().split())
q = deque()
q.append((a,1))
r = 0

while(q):
    n,t = q.popleft()
    if n > b:
        continue
    if n == b:
        print(t)
        break
    q.append((int(str(n)+"1"),t+1))
    q.append((n*2,t+1))
else:
    print(-1)

complexity

log m time because it depends on how many calculations we do before m reaches n or it meets the recurisve end condition. But it is log because when you repeatedly divide a number by 2 or remove its last digit, you are essentially performing logarithmic operations.

Let's break down the two cases:

1. Divide by 2 (if even): This is effectively a right shift in binary representation, and each right shift reduces the value by a factor of 2.

2. Remove the last digit (if ends with 1): This operation removes the least significant digit, and each removal is similar to dividing by 10.

Both operations lead to a reduction in the size of the number, and the number of such operations needed to reach n is logarithmic in the value of m. Therefore, the time complexity is logarithmic, specifically O(log m).

o (1) space