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

Advertisements

Pages: 1 2

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

Perl version return ! mod($a,5);

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

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.

Or, here’s an iterative version that uses a non-restoring binary division algorithm to compute the remainder.

class multiply {

}

I like the finite state machine and recursive mod solutions.

A Python solution based on bisection:

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

isvery fast, and it’s specific to Gambit Scheme:with resulting times

Converting the number to a string and checking the last digit would take a lot longer:

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

Another solution in Ruby using a modified binary search algorithm.

Learning assembly MIPS. I’m using MARS to simulate it:

I made the mistake of trying

which immediately filled my 32GB memory with a list of multiples of 5:

So here’s a pseudo-R6RS version:

that computes

Here’s a solution in C++.

Example:

Two Perl6 solutions:

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

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.

Example:

(my recent solution assumes 64-bit integers)

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

Here’s the updated version without division.

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

Here’s a solution in C that uses binary long division.

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:

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

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