antivenom's blog

How to do this question mentioned under dfs/bfs/dijktra's category ?
By antivenom, history, 9 years ago, In English

How to solve this question with the help of dfs/bfs/dijktra(as mentioned in ahmed-aly.com).This particular question has not been discussed much and don't have good resources to know about it.

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I managed to solve this : Code

The main idea is to do a BFS, with the nodes being the pair(mod value , sum of digits).

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Dude what made you come up with bfs ? Can you add comments in your code l'il bit :)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I can tell you how my code works. The start node is when the number is empty (0) with sum of digs and mod value is 0. We are doing the BFS since we need to find the minimum positive integer(which can be seen as shortest distance in the integer tree). Now if our element has a mod value 0 and sum of digits as N , then this is indeed our number and this is the shortest (since we are doing BFS , the first occurrence is indeed the smallest). Else what we try to do is append a digit [0-9] and mark this as a new node in the tree.

      In code , the first two functions are basic ones. The bfs is also the basic one. I am using "lwr" variable to see if the digit can be 0 or not. This is done just to avoid leading zeroes.

      You can ask if you have any doubts related to any part of code.

      → Reply