Блог пользователя antivenom

How to do this question mentioned under dfs/bfs/dijktra's category ?
Автор antivenom, история, 9 лет назад, По-английски

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.

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    9 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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.

      → Ответить