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.
Programming Praxis 
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 nzRuby:
{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}.”
“`
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](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 :-)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:
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)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; } } } } }Simple brute-force solution. Goes through multiples of 23 and tests weather they contain just 9s and 0s:
>>> from itertools import count >>> next(m for m in count(23, 23) if set(str(m)) == {'0', '9'}) 990909:)
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.
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 + rRunning 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