MINDSUM doubt

general
,
1

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

2

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.)

3

thank u so much for your time!