title: Smallest multiple having only 0 and 4 as its digits
body: <p>Given a number A find the smallest number B, such that A * B contains digits 4 and 0 only and zeroes should only be in the end i.e. numbers like 404 are not valid.</p>
  
  <p>For example:</p>
  
  <pre><code>| A | B   | A*B |
  |---|-----|-----|
  | 1 | 4   | 4   |
  | 2 | 2   | 4   |
  | 3 | 148 | 444 |
  | 4 | 1   | 4   |
  | 5 | 8   | 40  |
  </code></pre>
  
  <hr>
  
  <p>Well, I attempted the question in this manner. Maintain a queue of integers. The smallest possible number is 4. </p>
  
  <pre><code>Pop the number (i.e. the front element of the queue) and push the numbers that can be derived from this popped number. 
  That is , when we pop 4, we push (4*10) = 40 and (4*10 + 4) = 44 with the constraint that the popped number is not divisible by 10. If it is, push only its next multiple of 10.
  </code></pre>
  
  <p>So, my queue will be like: 4,40,44,400,440,444,.... </p>
  
  <p>As I am popping elements from the queue, I'll check if it is divisible the given number A. If yes, just break and the number popped is my desired result.</p>
  
  <p>Because my number can be really large, I maintained a queue of <code>pair&lt;string,int&gt;</code> where string corresponds to the <code>number</code> and int corresponds to the <code>remainder</code>. Thus, remainder of the next stage can be computed easily.</p>
  
  <p>Ex: </p>
  
  <pre><code>queue : &lt;"4",4&gt; 
  Pop , current result is string : "4" and remainder is lets say prev = 4
  check if the last digit is 0 or not (for checking if its a multiple of 10 or not)
  If not, then append 0 to this string and remainder as (prev*10)%a and push this pair in the queue. Also, append 4 to this string with remainder as : (prev*10 +4)%a and push. If the last digits is 0, append 0(not 4) and corresponding remainder, push this pair in the queue.
  
  Queue: &lt;"40",(prev*10)%a&gt;, &lt;"44", (prev*10 +4)%a&gt; and so on..
  </code></pre>
  
  <p>Till the pair in the front of the queue has remainder 0, we'll continue doing this.</p>
  
  <p>Though this improvement seemed to be a bit good, but not correct and didn't pass all the test cases. Can someone please throw some light on how this should be solved in an optimal manner. (The range of A is 10^10).</p>