By divad, 4 days ago,

Introduction

This is a tutorial/explanation on how DFS and BFS can be used for the following problem: 1141A - Game 23

Statement

We are given two integers $n$ and $m$ and are asked to determine in how many steps can we tranform $n$ to $m$ with the following steps:

• multiply $n$ by $2$
• multiply $n$ by $3$

If $n$ can not be made equal to $m$ using the transformations mentioned above then the answer show be $-1$

Solution

Let's try and visualize the following example: $120, 51840$

The highlighted path is the one from $n$ to $m$, so we can see that it takes $7$ transformations

Observations:

• every number generated is the form of $n \cdot 2^{k_1} \cdot 3^{k_2}$
• distance from $n$ to $n \cdot 2^{k_1} \cdot 3^{k_2}$ is $k_1 + k_2$
• the tree follows this rule:

• there is one particular case where $n = m$, then the answer is $0$

Now that we know what rule it follows we can generate the tree itself. But since we want to know if a path exists from $n$ to $m$ we can use any graph treversal algorithm, in this blog im going to show you how it can be done using DFS and BFS.

So that we dont generate a number multiple times we will use a frequency array. The problem is that we haven’t got enough memory to store for each number up to $10^{18}$. As mentioned before all numbers generated are in the form of $n \cdot 2^{k_1} \cdot 3^{k_2}$ so we can use a frequency matrix in which $viz[i][j]$ is equal to $1$ if $n \cdot 2^{i} \cdot 3^{j}$ has already been generated, or $0$ it that numbers has not been generated yet

Implementation

DFS implementation
BFS implementation

• 0

 » 3 days ago, # |   0 multiply n by 2 multiply m by 3 That m should be n according to the problem statement. Regardless of that, your approach is interesting.
•  » » 3 days ago, # ^ |   0 Thanks for pointing that out. I have now changed it