June 19, 2015 9:00 AM
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.
Posted by programmingpraxis
Categories: Exercises
Tags:
Mobile Site | Full Site
Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.
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 nzBy Paul on June 19, 2015 at 10:45 AM
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}
By naushniki on June 19, 2015 at 1:19 PM
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}.”
“`
By naushniki on June 19, 2015 at 1:27 PM
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]By Mike on June 19, 2015 at 10:30 PM
(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 :-)By mitch on June 20, 2015 at 2:36 AM
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)
By Jussi Piitulainen on June 20, 2015 at 6:53 AM
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)By matthew on June 20, 2015 at 5:22 PM
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; } } } } }By haari52 on June 20, 2015 at 7:21 PM
Simple brute-force solution. Goes through multiples of 23 and tests weather they contain just 9s and 0s:
By Brett Warren on June 22, 2015 at 12:29 PM
>>> from itertools import count >>> next(m for m in count(23, 23) if set(str(m)) == {'0', '9'}) 990909:)
By Jussi Piitulainen on June 22, 2015 at 12:48 PM
Given the problem, why isn’t the answer for n to be 0?
By Andrew Au on June 23, 2015 at 5:15 AM
@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.
By Jussi Piitulainen on June 23, 2015 at 6:12 AM
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;
}
}
}
By Leandro Araujo on June 23, 2015 at 11:12 AM
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”.
By soap on June 25, 2015 at 9:21 AM
I’ve streamlined my last a little.
my $x=23;
my $y=1;
while (($x * $y) =~ /[1-8]/) {
$y++;
}
print $x * $y . “\n”;
By soap on June 25, 2015 at 11:40 AM
@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.)
By Jussi Piitulainen on June 25, 2015 at 1:37 PM
@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++;
}
By soap on June 25, 2015 at 3:55 PM
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:
By Globules on June 29, 2015 at 5:00 AM
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
By pollyhancock on July 14, 2015 at 10:25 AM
R7RS Scheme solution:
https://notabug.org/PangolinTurtle/praxis-solutions/raw/master/2015-06-19.scm
By UndeadPotato on July 20, 2015 at 1:31 PM