I was trying this problem with different approach (as bfs is used by most of users). I can’t find where i am going wrong.I ran a hell lot of test cases on my code as well as on accepted ones and all of them matched.kindly help!

MY solution:here

I was trying this problem with different approach (as bfs is used by most of users). I can’t find where i am going wrong.I ran a hell lot of test cases on my code as well as on accepted ones and all of them matched.kindly help!

MY solution:here

Hi, **@humblejumbo.**

It turns out that some version of a tree search is needed. Your solution doesn’t search a tree; it goes down a single branch.

To illustrate, consider the inputs **N=7, D=32.** The ultimate minimum value is 1, which your solution arrives at as follows:

Lines 33-35 when **i==6**… (For 0 <= i <= 5, *p.first* is a value > 1.)

```
for(ll i=0;i<=9;i++)
{
pair<int,int> p=digitsum(n+d*i,i);
```

p == digitSum(7 + 6*32, 6) == digitSum(199,6) -> digitSum(19,7) -> digitSum(10,8) -> the pair **{ 1, 9 }**

Thus your solution prints **1 9**. But the optimal solution arrives at 1 in *8 steps*, which is only uncovered by running a full search of the tree of possibilities.

- Steps 1-3: 7 + 3 x 32 = 103.
- Step 4: DigitSum(103) = 4.
- Steps 5-7: 4 + 3 x 32 = 100.
- Step 8: DigitSum(100) = 1.

So you are correct that your approach is different – it does not consider all possibilities that a full search of the tree would uncover. (A breadth first approach is most efficient, since a depth-first search would likely go deeper than necessary on some branches in search of the optimal result.)

thank u so much for your time!