Nines And Zeros

June 19, 2015

We have today an interview question that so stumped an interviewee that he asked for help on the internet:

Given an integer n, find the smallest number consisting only of the digits zero and nine that is divisible by n. For instance, given n = 23, the smallest number consisting only of the digits zero and nine that is divisible by 23 is 990909.

Your task is to write a program that finds the number described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

20 Responses to “Nines And Zeros”

  1. Paul said

    In Python3.

    import itertools
    
    def _gen09(n):
        if n == 1:
            yield 9
        else:
            for x in _gen09(n - 1):
                xx = 10 * x
                yield xx
                yield xx + 9
    
    def nine_zero(n):
        for i in itertools.count(1):
            for nz in _gen09(i):
                if nz % n == 0:
                    return nz
    
  2. naushniki said

    Ruby:

    {code}
    divider = ARGV[0].to_i
    answer = 1

    while answer.to_s(2).gsub(‘1’, ‘9’).to_i % divider != 0
    answer += 1
    end

    answer = answer.to_s(2).gsub(‘1’, ‘9’)
    puts “The smallest number consisting only of the digits zero and nine that is divisible by #{divider.to_s} is #{answer.to_s}.”
    {code}

  3. naushniki said

    Ruby:

    “`
    divider = ARGV[0].to_i
    answer = 1

    while answer.to_s(2).gsub(‘1′, ‘9’).to_i % divider != 0
    answer += 1
    end

    answer = answer.to_s(2).gsub(‘1′, ‘9’)
    puts “The smallest number consisting only of the digits zero and nine that is divisible by #{divider.to_s} is #{answer.to_s}.”
    “`

  4. Mike said
    from collections import deque
    
    def f(n):
        d = deque([9])
        while d[0] % n:
            x = 10*d.popleft()
            d.extend((x, x+9))
        return d[0]
    
  5. mitch said
    (defun test90 (n)
      (if (< n 10) 
          (or (= n 9) (= n 0))
        (and (test90 (/ n 10))
    	 (test90 (% n 10)))))
    
    (defun nineohs (n)
      (let ((i 1)
    	(ni n))
        (while (not (test90 ni))
          (setq i (+ i 1))
          (setq ni (* i n)))
        i))
    
    ;; Interestingly, if you run this a bit, you get a nice little sequence:
    ;; (loop for i from 1 to 20 collect (nineohs i))
    ;;   => (9 45 3 225 18 15 1287 1125 1 9 9 75 693 6435 6 5625 5877 5 5211 45)
    ;;
    ;; Which is sequence number A096688 over at OEIS.org, but we knew that already :-)
    
  6. Jussi Piitulainen said

    Surely 0 is the smallest number that, in so far as numbers consist of digits, consists of only 0s and 9s and is divisible by the given integer? I’m allowing that negative numbers don’t consist of only digits, having also a sign, and the given integer is not 0. Also, I suspect the interviewee just failed to consider brute force as a solution :)

    Here’s using standard Scheme to reinterpret the binary of a counter as decimal.

    (define (f n)
      (do ((k 1 (+ k 1))
           (m 9 (* 9 (string->number (number->string (+ k 1) 2) 10))))
          ((zero? (modulo m n)) m)))

    And here’s how it does.

    > (load "90.scm")
    > (f 23)
    990909
    > (map f '(1 2 3 4 5 6 7 8 9))
    (9 90 9 900 90 90 9009 9000 9)

  7. matthew said

    Here’s a couple of solutions in Haskell, based on filtering the infinite sequence 9,90,99,900,909…

    In the first case we construct the sequence directly we use a recursive interleaving, in the second, inspired by Mike’s deque solution above, we use the old functional queue trick:

    interleave (a:s) t = a:interleave t s
    s = 9:interleave t (map (+ 9) t) where t = map (* 10) s
    
    f [] t = f (reverse t) []
    f (n:s) t = n : f s (m+9:m:t) where m = 10*n
    t = f[9][]
    
    
    main = 
         print (take 10 $ filter ((== 0).(`mod` 23)) s) >>
         print (take 10 $ filter ((== 0).(`mod` 23)) t)
    
  8. haari52 said
    public class SmallestNumber {
    
    	/**
    	 * @param args
    	 */
    	public static void main(String[] args) {
    		Scanner scanner = new Scanner(System.in);
    		System.out.println("Enter the number ");
    		int number = scanner.nextInt();
    		boolean status = true;
    		for(int i = 2*number;status ;i+=number){
    			if(i % number == 0){
    				int temp = i;
    				while(status && temp != 0){
    					if((temp % 10 == 0 || temp % 10 == 9) ){
    					temp  = temp/10;
    					status = true;
    				}
    				else{
    					status = false;
    				}
    			}
    			if(status){
    				System.out.println(i);
    				status = false;
    			}
    			else{
    				status = true;
    			}
    		}
    		 
    	}
    
    }
    }
    
  9. Brett Warren said

    Simple brute-force solution. Goes through multiples of 23 and tests weather they contain just 9s and 0s:

    from itertools import count
    
    def smallest_nines_zeros(diviser):
    	for n in count(1):
    		candidate = n*diviser
    		
    		exclusivly_nines_zeros = all(
    			[num in ["0", "9"] for num in str(candidate)]
    		)
    		
    		if exclusivly_nines_zeros:
    			return candidate
    
    if __name__  == "__main__":
    	print(smallest_nines_zeros(23))
    
  10. Jussi Piitulainen said
    >>> from itertools import count
    >>> next(m for m in count(23, 23) if set(str(m)) == {'0', '9'})
    990909
    

    :)

  11. Andrew Au said

    Given the problem, why isn’t the answer for n to be 0?

  12. Jussi Piitulainen said

    @Andrew, by way of discussion: In this problem, the interviewer clearly does not consider 0 to be a number, because allowing 0 would be incompatible with the example given in the problem statement itself: “Given an integer n, find the smallest number consisting only of the digits zero and nine that is divisible by n. For instance, given n = 23, the smallest number consisting only of the digits zero and nine that is divisible by 23 is 990909.”

    And could we allow n = 0? Because surely 0 is an integer even if it’s not a number? We could maybe say that a number is divisible by 0 if it’s a multiple of 0, but the only such number is 0, and in this problem 0 is not a number, so oops :)

    I think the interviewer would appreciate a two-step approach: point out that the problem statement could be improved, and then proceed with the intended interpretation. If they are evaluating our ability to write such specs, the first step might be rather important.

  13. Leandro Araujo said

    I’m just a begginer on programming, but there’s my program.

    c#

    using System;

    namespace SampleNamespace
    {
    public class SampleClass
    {
    public static void Main()
    {
    int n = 23;
    double x = 1;
    double result;

    result = n * x;

    while (validador(result.ToString())){
    result = n * x++;
    }
    Console.WriteLine(result);
    }

    public static bool validador(string num){
    string validstr = “12345678”;
    int x;

    for (x = 0; x <= 7; x++){
    if (num.Contains(validstr.Substring(x,1))){
    return true;
    }
    }
    return false;
    }
    }
    }

  14. soap said

    Now I’m no programmer (I guess that’s why I’m here) but this is what I produced in perl.

    my $x=23;
    my $y=1;
    my $done=0;
    while ($done == 0) {
    if (($x * $y) !~ /[1-8]/) {
    print $x * $y . “\n”;
    $done = 1;
    }
    $y++;
    }

    Incidentally, for those that keep asking why zero isn’t the answer, the clue is in the question, the answer is “the smallest number consisting only of the digits zero AND nine”.

  15. soap said

    I’ve streamlined my last a little.

    my $x=23;
    my $y=1;
    while (($x * $y) =~ /[1-8]/) {
    $y++;
    }
    print $x * $y . “\n”;

  16. Jussi Piitulainen said

    @soap Would a number consisting of all 9s not be a solution, then? Not for 23, of course, but for, say, 3, or 33. Does your own code print both 0s and 9s for those? (No.)

  17. soap said

    @Jussi, yes it would, well spotted.

    My original code (below) worked, (I’ve retested using 11 as in the input value) but I got ahead of myself trying to make it more compact.
    For some reason I am yet to understand, when testing multiple values in while() using ‘and’ the tests are not cumulative, instead if any one test returns true then the loop is triggered.

    Like I said, I’m not a programmer. :¬)

    Original:

    my $x=23;
    my $y=1;
    my $done=0;
    while ($done == 0) {
    if (($x * $y) =~ /[0]/ and ($x * $y) =~ /[9]/ and ($x * $y) !~/[1-8]/) {
    print $x * $y . “\n”;
    $done = 1;
    }
    $y++;
    }

  18. Globules said

    Another Haskell solution.

    firstDivBy :: Integer -> Integer
    firstDivBy n = head . dropWhile ((/=0) . flip rem n) $ map ((9*) . f) [1..]
      where f 0 = 0
            f n = let (q, r) = n `quotRem` 2 in 10 * f q + r
    

    Running it we get:

    λ> firstDivBy 23
    990909
    λ> 
    
  19. pollyhancock said

    I can offer a no-frills Haskell solution: the first element of the list of numbers drawn from the multiples of 23 that has the property that all the characters in its string representation are elements of the string “90”:

    Prelude> head [ n | n <- [23,46..], all (`elem` "90") (show n) ]
    990909

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: