Smallest number consisting of only ones and zeroes, divisible by a given number. Problem statement: Link to the problem here. Find the smallest number consisting of only ones and zeroes, which is divisible by a given number n.
Solution approach:

Let's represent our numbers as strings here. Now, consider there are N
  states, where i'th state stores the smallest string which when take
  modulo with N gives i. Our aim is to reach state 0. Now, we start from
  state "1" and at each step we have two options, either to append "0"
  or "1" to current state. We try to explore both the options, but note
  that if I have already visited a state, why would I visit it again? It
  already stores the smallest string which achieves that state and if I
  visit it again with a new string it will surely have more characters
  than already stored string.

My doubt:
I don't understand the fact why we are not further visiting a number which has a state that has already been visited. I understand that another number which had the same state previously will be smaller. But what if the actual answer lies in the numbers obtained by appending ones or zeroes to the current number with the same state rater than the previous smaller number with the same state? Can we prove that we can safely ignore this larger number with the repeated state?
 A: 
Note: This user correctly gave the answer in the comments,
  however did not post it as an anwer, even after i asked him to do so.
  So, after waiting for months, i am posting the answer here.

If X and Y are same modulo M, then XC + Z and Y C + Z also have same modulo M. Multiplication and addition might change the modulo's value, but it would be the same change for both numbers, hence they will end up with same modulo, which might still be difference from the initial modulo.
Also, this can be understood using residue sets as well, tough it might be an overkill. If we have a set S which has all it's elements unique modulo M, and has one entry for each modulo possible, i.e. it is an complete residue set, then multiplying all terms of the set with a constant C will give us another complete residue set. Now adding Z to all elements of the set will again give us a complete residue set. Now use this on two complete residue sets, which have all elements same expect X and Y. To finally get a complete residue set, operation on X and Y will have to correspond to the same modulo in the final set.
