Multiples Of 5
June 12, 2018
We have today an interview question from Amazon:
Write a program to determine if an integer is a multiple of 5 in O(log n) time complexity. You cannot use the division or modulus operators.
Your task is to solve the Amazon interview question. 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 
(define (mult5 i)
(let* ((s (number->string i))
(n (string-length s)))
(memv (string-ref s (- n 1)) ‘(#\0 #\5))))
Some out-of-the-box approach to it, using Julia:
code:
function IsMultipleOf5(x::Int64)
X = string(x)
z = parse(Int64, X[end])
return (z == 0)||(z == 5)
end
testing:
IsMultipleOf5(150)
true
IsMultipleOf5(15)
true
IsMultipleOf5(12)
false
I’m not sure about the O() of this code, but it’s definitely faster than brute-forcing the problem.
In Python. I do not think that converting the number to string is a real solution, as it is not easy to write this conversion without div and mod.
from itertools import takewhile, count def is_div_5(n): powers = reversed(list(takewhile(lambda i: i <= n, (5**i for i in count(1))))) for p in powers: while n >= p: n-= p return n == 0Perl version return ! mod($a,5);
print dn( 987, 5 ) ? 'T':'F',"\n"; print dn( 985, 5 ) ? 'T':'F',"\n"; sub dn { return ! mod(0+$_[0],$_[1]); } sub mod { $_[2]||=$_[1]; $_[0] = mod( @_[0,1], $_[1]*$_[2] ) if $_[1] >= $_[1]*$_[2]; $_[0] -= $_[1] while $_[0] >= $_[2]; return $_[0] }def is_multiple_five(n):
return str(n)[-1] in [“0″,”5”]
If we are going to do string manip and assume “integer”s
[sourcecode lang="perl"]
sub mult5{shift=~/[05]$/}
[sourcecode]
Ooops… If we are going to do string manip and assume “integer”s
sub mult5{shift=~/[05]$/}Build a finite-state machine to process the bits right to left.
bool mult5(unsigned int n) {
unsigned short state = 0;
while (n != 0) {
switch (state) {
case 0:
state = (n & 1) ? 2 : 0;
break;
case 1:
state = (n & 1) ? 0 : 3;
break;
case 2:
state = (n & 1) ? 3 : 1;
break;
case 3:
state = (n & 1) ? 1 : 4;
break;
case 4:
state = (n & 1) ? 4 : 2;
break;
}
n >>= 1;
}
return (state == 0);
}
What the hell? Overcomplicating solutions won’t get you the job, either.
Python.
Define a recursive mod() function and use that to check if n % 5 == 0.
def mod(n,d): if n >= d: n = mod(n, d<<1) if n >= d: n -= d return n def isDivisibleBy5(n): return mod(n, 5) == 0Or, here’s an iterative version that uses a non-restoring binary division algorithm to compute the remainder.
def mod(n, d): k = d while k < n: k <<= 1 while k >= d: if n < 0: n += k else: n -= k k >>= 1 if n < 0: n += d return nclass multiply {
}
I like the finite state machine and recursive mod solutions.
A Python solution based on bisection:
# divisibility by 5 without using division or remainder operations # # find solution of f(q) = 0 # f(q) = 5*q - n # if q is integer, then n is divisible by 5 # start with 1 and multiply by 2 until greater than n # bisection on f(q) using stored powers of 2 def div5(n): n = abs(n) i = 0 p = [1] while p[i] <= n: p.append(2*p[i]) i = i + 1 a, b = 0, p[i] # we have and maintain f(a)<=0, f(b)>0 while i > 0: i = i - 1 mid = a + p[i] if 5*mid - n > 0: b = mid else: a = mid return 5*a - n == 0 if __name__ == "__main__": print([ n for n in range(-26, 26) if div5(n) ])Surprisingly, no-one has looked into the Log(10) option yet:
function imo5(x::Int64)
if x == 0; return true; end
if x < 0; x = -x; end
z = floor(log(10, x))
end
After all, what are logarithms if not a quicker way to do division, multiplication, and powers?
:) If you allow floating point numbers, logarithms and exponentials then you can do
Here’s a silly program, but it is very fast, and it’s specific to Gambit Scheme:
;;; 2^4 mod 5 = 1 ;;; so if the number is < 16, check whether it's ;;; 0, 5, 10, or 15 ;;; Otherwise, sum base 16 digits and recurse. ;;; This can be done with digits of 16 or 32 bits. ;;; Using Gambit's internal representation of bignums in ;;; the C back end. (declare (standard-bindings) (extended-bindings) (block) (mostly-fixnum) (not safe)) (define (multiple-of-5 n) (cond ((##bignum? n) (multiple-of-5 (let ((k (##bignum.mdigit-length n))) (do ((i 0 (fx+ i 1)) (sum 0 (+ sum (##bignum.mdigit-ref n i)))) ((fx= i k) sum))))) ((fx< n 16) (##not (##not (memv n '(0 5 10 15))))) (else (multiple-of-5 (do ((n n (fxarithmetic-shift-right n 4)) (sum 0 (+ sum (fxand n 15)))) ((fxzero? n) sum))))))with resulting times
> (define x (expt 5 100000000)) > (time (multiple-of-5 x)) (time (multiple-of-5 x)) 36 ms real time 33 ms cpu time (32 user, 0 system) no collections no bytes allocated 1 minor fault no major faults #tConverting the number to a string and checking the last digit would take a lot longer:
> (time (let () (number->string x) #f)) (time (let () (number->string x) #f)) 288437 ms real time 246291 ms cpu time (211867 user, 34423 system) 96 collections accounting for 22225 ms real time (11020 user, 8452 system) 3367493584 bytes allocated 6867449 minor faults no major faultsIn Ruby. Using built-in Binary Search which has O(log n) charateristics.
def multiple_of_5?(n) !!(0..n).bsearch { |x| n <=> (x * 5) } endAnother solution in Ruby using a modified binary search algorithm.
def multiple_of_5?(n) l = 0 r = n - 1 while l <= r do m = (l + r) >> 1 # Divide by 2 by right shifting 1 bit if m * 5 < n l = m + 1 elsif m * 5 > n r = m - 1 else return true end end false endLearning assembly MIPS. I’m using MARS to simulate it:
.globl main # Max digits for the number read from the standard input. .eqv MAX_CHARACTERS_INPUT 50 # Syscall used in this program. .eqv READ_STRING 8 .eqv PRINT_STRING 4 .eqv EXIT_SUCCESS 10 .data # Input number from standard input. INPUT: .byte 0:MAX_CHARACTERS_INPUT # Output to print to the standard output. TRUE: .asciiz "true\n" FALSE: .asciiz "false\n" .text # $a0 -> address of string to print to the standard output. .macro print_string li $v0, PRINT_STRING syscall .end_macro .eqv $STRING_ADDRESS $s0 .eqv $NEWLINE $s1 .eqv $CHECK_ZERO $s2 .eqv $CHECK_FIVE $s3 .eqv $CHARACTER $t0 main: la $STRING_ADDRESS, INPUT li $NEWLINE, '\n' li $CHECK_ZERO, '0' li $CHECK_FIVE, '5' # Read the number from the standard input. li $v0, READ_STRING move $a0, $STRING_ADDRESS li $a1, MAX_CHARACTERS_INPUT syscall # Find the last digit. while_last_digit: lb $CHARACTER, ($STRING_ADDRESS) beq $CHARACTER, $NEWLINE, end_string addi $STRING_ADDRESS, $STRING_ADDRESS, 1 j while_last_digit end_string: lb $CHARACTER, -1($STRING_ADDRESS) # Check if the number is divisible by five. beq $CHARACTER, $CHECK_ZERO, is_multiple_of_five beq $CHARACTER, $CHECK_FIVE, is_multiple_of_five la $a0, FALSE print_string j exit is_multiple_of_five: la $a0, TRUE print_string exit: li $v0, EXIT_SUCCESS syscallI made the mistake of trying
> (define x (time (expt 5 10000000))) (time (expt 5 10000000)) 366 ms real time 366 ms cpu time (330 user, 36 system) 5 collections accounting for 6 ms real time (4 user, 2 system) 594128 bytes allocated 34037 minor faults no major faults > (time (mult5? x))which immediately filled my 32GB memory with a list of multiples of 5:
So here’s a pseudo-R6RS version:
;;; 2^4 mod 5 = 1 ;;; so if the number is < 16, check whether it's ;;; 0, 5, 10, or 15 ;;; Otherwise, sum base 16 digits and recurse. ;;; This can be done with digits of 16 or 32 bits. (declare (standard-bindings) (extended-bindings) (block) (mostly-fixnum) (not safe)) ;; Gambit definitions of R6RS procedures (define (bitwise-bit-field ei1 ei2 ei3) (extract-bit-field (- ei3 ei2) ei2 ei1)) (define (bitwise-length ei) (integer-length ei)) ;;; R6RS code. (define (multiple-of-5 n) (let ((n (abs n))) (cond ((>= n 65536) ;; sum the base 65536 digits of n (multiple-of-5 (let ((k (bitwise-length n))) (do ((i 0 (+ i 16)) (sum 0 (+ sum (bitwise-bit-field n i (+ i 16))))) ((>= i k) sum))))) ((>= n 16) ;; sum the base 16 digits of n (multiple-of-5 (do ((n n (arithmetic-shift n -4)) (sum 0 (+ sum (bitwise-and n 15)))) ((zero? n) sum)))) (else (not (not (memv n '(0 5 10 15)))))))) (define (mult5? n) (let outer ((n (abs n)) (power5 (list 5))) (if (< (* (car power5) 5) n) (outer n (cons (* (car power5) 5) power5)) (let inner ((n n) (power5 power5)) (if (null? power5) (zero? n) (if (< n (car power5)) (inner n (cdr power5)) (inner (- n (car power5)) power5)))))))that computes
> (time (multiple-of-5 x)) (time (multiple-of-5 x)) 133 ms real time 133 ms cpu time (129 user, 4 system) 10 collections accounting for 8 ms real time (4 user, 4 system) 46440928 bytes allocated 835 minor faults no major faultsHere’s a solution in C++.
#include <cstdlib> #include <iostream> #include <stack> #include <string> using namespace std; bool multiple(unsigned number, unsigned multiplier) { if (multiplier == 0) return false; if (multiplier == 1) return true; stack<unsigned> powers; unsigned power = 1; while (power <= number) { power *= multiplier; powers.push(power); } while (number >= multiplier) { while (number >= powers.top()) { number -= powers.top(); } powers.pop(); } return number == 0; } int main(int argc, char* argv[]) { if (argc < 2 || argc > 3) { cout << "Usage: " << argv[0] << " NUMBER [MULTIPLIER]" << endl; return EXIT_FAILURE; } int number = stoi(argv[1]); int multiplier = 5; if (argc == 3) multiplier = stoi(argv[2]); cout << multiple(number, multiplier) << endl; return EXIT_SUCCESS; }Example:
Two Perl6 solutions:
sub is-multiple-of-five(Int:D $n) { my $last-digit = $n mod 10; $last-digit == 5 or $last-digit == 0; } sub is-multiple-of-five-v2(Int:D $n is copy) { my @powers = reverse powers-of-five-upto($n); while $n > 0 and @powers { $n -= @powers.head; if @powers.head > $n { shift @powers; } } $n == 0; } sub powers-of-five-upto(Int:D $n) { my @powers = [5]; while @powers.tail * 5 < $n { @powers.push: (@powers.tail * 5); } @powers; } for [-1, 0, 3, 5, 11, 25, 33, 50, 70, 100] -> $i { say "is-multiple-of-five($i) = " ~ is-multiple-of-five($i) ~ " is-multiple-of-five-v2($i) = " ~ is-multiple-of-five-v2($i); } # is-multiple-of-five(-1) = False, is-multiple-of-five-v2(-1) = False # is-multiple-of-five(0) = True, is-multiple-of-five-v2(0) = True # is-multiple-of-five(3) = False, is-multiple-of-five-v2(3) = False # is-multiple-of-five(5) = True, is-multiple-of-five-v2(5) = True # is-multiple-of-five(11) = False, is-multiple-of-five-v2(11) = False # is-multiple-of-five(25) = True, is-multiple-of-five-v2(25) = True # is-multiple-of-five(33) = False, is-multiple-of-five-v2(33) = False # is-multiple-of-five(50) = True, is-multiple-of-five-v2(50) = True # is-multiple-of-five(70) = True, is-multiple-of-five-v2(70) = True # is-multiple-of-five(100) = True, is-multiple-of-five-v2(100) = TrueA solution in Racket.
Since 2^4 = 16 mod 5 is 1, we can just add up the (precalculated) mod 5s of the hex digits of n:
a = list(range(5))*4; def mod5(n): s = 0 while n > 0: s += a[n & 15] n = n >> 4 while s >= 5: s -= 5 return s for i in range(20): print(i,i%5,mod5(i)) for i in range(100): assert(i%5 == mod5(i))I like @matthew’s solution. That’s a great idea.
Here’s a solution in C, using an approach from section 10-17 of Hacker’s Delight.
#include <stdbool.h> #include <stdio.h> #include <stdlib.h> bool mult5(unsigned n) { return n * 0xCCCCCCCCCCCCCCCD <= -1UL / 5; } int main(int argc, char* argv[]) { if (argc != 2) { fprintf(stderr, "Usage: %s INT\n", argv[0]); return EXIT_FAILURE; } unsigned n = strtoul(argv[1], NULL, 10); printf("%d\n", mult5(n)); return EXIT_SUCCESS; }Example:
(my recent solution assumes 64-bit integers)
I just realized my recent solution uses division :-(.
Here’s the updated version without division.
#include <stdbool.h> #include <stdio.h> #include <stdlib.h> bool mult5(unsigned n) { return n * 0xCCCCCCCCCCCCCCCD <= 0x3333333333333333; } int main(int argc, char* argv[]) { if (argc != 2) { fprintf(stderr, "Usage: %s INT\n", argv[0]); return EXIT_FAILURE; } unsigned n = strtoul(argv[1], NULL, 10); printf("%d\n", mult5(n)); return EXIT_SUCCESS; }Here’s a corresponding Python version (unlike the C version above, this works on arbitrary sized integers).
def mult5(n): lhs = 0xC rhs = 0x3 mask = 0xF while n > mask: lhs = (lhs << 4) | 0xC rhs = (rhs << 4) | 0x3 mask = (mask << 4) | 0xF lhs += 1 lhs = mask & (n * lhs) return lhs <= rhsHere’s a solution in C that uses binary long division.
#include <limits.h> #include <stdbool.h> #include <stdio.h> #include <stdlib.h> bool mult5(unsigned n) { unsigned q = 0; unsigned r = 0; unsigned b = sizeof(unsigned) * 8; for (unsigned i = b - 1; i < UINT_MAX; --i) { r <<= 1; r ^= (-(unsigned)(n >> i & 1) ^ r) & 1; if (r >= 5) { r -= 5; q |= 1 << i; } } return r == 0; } int main(int argc, char* argv[]) { if (argc != 2) { fprintf(stderr, "Usage: %s INT\n", argv[0]); return EXIT_FAILURE; } unsigned n = strtoul(argv[1], NULL, 10); printf("%d\n", mult5(n)); return EXIT_SUCCESS; }Example:
@Daniel: nice solution. Actually, @gambiteer seems to have first made the observation about 2^4 = 1 mod 5. This means that n >> 4k = n mod 5 for any n and we can do this:
#include <stdint.h> #include <assert.h> uint32_t mod5(uint32_t n) { n = (n & 0xffff) + (n >> 16); n = (n & 0xff) + (n >> 8); n = (n & 0x0f) + (n >> 4); n = (n & 0x0f) + (n >> 4); while (n >= 5) n -= 5; return n; } int main() { for (uint32_t n = 1; n != 0; n++) { assert(mod5(n) == n%5); } }I initially missed @gambiteer’s solution. That’s a nice approach.
Here’s a similar approach that processes one bit at a time, utilizing 2**i mod 5 = {1,2,4,3}[i%4].
def mult5(x): a = (1,2,4,3) while x > 10: y = 0 i = 0 while x: y += a[i] * (x & 1) x >>= 1 i += 1 i *= i <= 3 # i %= 4, w/o % x = y return x in (0,5,10)@programmingpraxis:
Your solution is $O((\log n)^2)$ in both space and time.
You compute a list of (approximately) $5^1$, $5^2$, …, $5^{\log n}$, which takes time and space proportional to $1+2+\cdots+\log n$, which is proportional to $(\log n)^2$.
Which is why it filled up the entire memory of my machine so quickly when I tried it on $5^{10,000,000}$.
I haven’t analyzed all the algorithms presented here, but I suspect that several others don’t satisfy the $O(\lot n)$ requirement except under very special circumstances.
When assuming 32-bit integers, for example, all algorithms are $O(1)$.
@Gambiteer: good point. Here’s a Python version of my solution up above that works on arbitrary length integers in log(n) time (ie. linear in the length of the binary representation). The number is repeatedly split into two halves and added (with a lower half of 4n bits, to preserve value mod5). 2^10000000000 is dealt with in a few seconds:
# mod 5 by repeated subtraction def reduce5(n): while n >= 5: n -= 5 return n # Return k, the smallest power of 2 such that 2^k > n def wordsize(n): k = 1 while (1<<k) <= n: k <<= 1 return k def mod5(n): # Simple case if n < 16: return reduce5(n) # Number of bits (as a power of 2) k = wordsize(n) # Add bottom k bits into rest of n # k always a multiple of 4 so preserves value mod 5 while k != 4: k >>= 1 n = (n >> k) + (n & ((1<<k)-1)); # We might have overflowed, so recurse return mod5(n) for i in range(1000000): assert(i%5 == mod5(i)) print(mod5((1<<10000000000)))