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

Pages: 1 2

### 33 Responses to “Multiples Of 5”

1. Sven said

(define (mult5 i)
(let* ((s (number->string i))
(n (string-length s)))
(memv (string-ref s (- n 1)) ‘(#\0 #\5))))

2. Zack said

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.

3. Paul said

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 == 0
```
4. Perl version return ! mod(\$a,5);

```print dn( 987, 5 ) ? 'T':'F',"\n";
print dn( 985, 5 ) ? 'T':'F',"\n";

sub dn { return ! mod(0+\$_,\$_); }

sub mod {
\$_||=\$_;
\$_ = mod( @_[0,1], \$_*\$_ ) if \$_ >= \$_*\$_;
\$_ -= \$_ while \$_ >= \$_;
return \$_
}
```
5. Osvaldo Peroncini said

def is_multiple_five(n):
return str(n)[-1] in [“0″,”5”]

6. If we are going to do string manip and assume “integer”s

[sourcecode lang="perl"]
sub mult5{shift=~/\$/}
[sourcecode]

7. Ooops… If we are going to do string manip and assume “integer”s

```sub mult5{shift=~/\$/}
```
8. 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);
}

9. Josh said

One solution is to use your language’s features to convert the input number to a string, then examine the last digit of the string, but that probably won’t get you a job at Amazon.

What the hell? Overcomplicating solutions won’t get you the job, either.

10. Mike said

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) == 0

```

Or, 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 n
```
11. aparna said

class multiply {

``````static int multiply(int x, int y) {
if (y == 0)
return 0;

if (y > 0)
return (x + multiply(x, y - 1));

if (y < 0)
return -multiply(x, y);

return -1;
}
public static void main(String[] args) {

System.out.print("\n" + multiply(5, 11));
}
``````

}

12. Jan Van lent said

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 = 
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) ])
```
13. Zack said

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

``````while z > 0
x -= 10^z
z = floor(log(10, x))
end

return (x==5)||(x==0)
``````

end

After all, what are logarithms if not a quicker way to do division, multiplication, and powers?

14. Jan Van lent said

:) If you allow floating point numbers, logarithms and exponentials then you can do

```imo5(x) = abs(n)+5 - 5*floor(5^(log(5, abs(n)+5) - 1)) == 0.0
```
15. Gambiteer said

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
#t
```

Converting 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 faults
```
16. V said

In Ruby. Using built-in Binary Search which has O(log n) charateristics.

```def multiple_of_5?(n)
!!(0..n).bsearch { |x| n <=> (x * 5) }
end
```
17. V said

Another 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
end
```
18. Moka said

Learning 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 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 \$NEWLINE           \$s1
.eqv \$CHECK_ZERO        \$s2
.eqv \$CHECK_FIVE        \$s3
.eqv \$CHARACTER         \$t0
main:
li \$NEWLINE, '\n'
li \$CHECK_ZERO, '0'
li \$CHECK_FIVE, '5'

# Read the number from the standard input.
li \$a1, MAX_CHARACTERS_INPUT
syscall

# Find the last digit.
while_last_digit:
beq \$CHARACTER, \$NEWLINE, end_string

j while_last_digit

end_string:

# 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
syscall
```
19. Gambiteer said

I 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:

```heine:~/programs/gambit/gambit> ps u | grep gsc
lucier   18144  9.0 92.8 48004268 30514636 pts/0 T  16:51   0:20 gsc
```

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 faults
```
20. Daniel said

Here’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 << " NUMBER [MULTIPLIER]" << endl;
return EXIT_FAILURE;
}
int number = stoi(argv);
int multiplier = 5;
if (argc == 3) multiplier = stoi(argv);
cout << multiple(number, multiplier) << endl;
return EXIT_SUCCESS;
}
```

Example:

```\$ g++ -std=c++11 -Wall -Wextra -Wpedantic -o multiple multiple.cpp

\$ ./multiple 987
0

\$ ./multiple 985
1
```
21. mcmillhj said

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 {

shift @powers;
}
}

\$n == 0;
}

sub powers-of-five-upto(Int:D \$n) {
my @powers = ;

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) = True
```
22. r. clayton said

A solution in Racket.

23. matthew said

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))
```
24. Daniel said

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);
return EXIT_FAILURE;
}
unsigned n = strtoul(argv, NULL, 10);
printf("%d\n", mult5(n));
return EXIT_SUCCESS;
}
```

Example:

```\$ ./multiple 987
0

\$ ./multiple 985
1
```
25. Daniel said

(my recent solution assumes 64-bit integers)

26. Daniel said

I just realized my recent solution uses division :-(.

27. Daniel said

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);
return EXIT_FAILURE;
}
unsigned n = strtoul(argv, NULL, 10);
printf("%d\n", mult5(n));
return EXIT_SUCCESS;
}
```
28. Daniel said

Here’s a corresponding Python version (unlike the C version above, this works on arbitrary sized integers).

```def mult5(n):
lhs = 0xC
rhs = 0x3
lhs = (lhs << 4) | 0xC
rhs = (rhs << 4) | 0x3
lhs += 1
lhs = mask & (n * lhs)
return lhs <= rhs
```
29. Daniel said

Here’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);
return EXIT_FAILURE;
}
unsigned n = strtoul(argv, NULL, 10);
printf("%d\n", mult5(n));
return EXIT_SUCCESS;
}
```

Example:

```\$ ./mult5 987
0

\$ ./mult5 985
1
```
30. matthew said

@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);
}
}
```
31. Daniel said

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)
```
32. Gambiteer said

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

33. matthew said

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