## 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 byn. For instance, givenn= 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.

Advertisements

Pages: 1 2

In Python3.

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}

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}.”

“`

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)

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:

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

:)

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

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

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;

}

}

}

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

I’ve streamlined my last a little.

my $x=23;

my $y=1;

while (($x * $y) =~ /[1-8]/) {

$y++;

}

print $x * $y . “\n”;

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

@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++;

}

Another Haskell solution.

Running it we get:

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

R7RS Scheme solution:

https://notabug.org/PangolinTurtle/praxis-solutions/raw/master/2015-06-19.scm