Multiples Of 5
June 12, 2018
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.
Division is nothing more than repeated subtraction, and subtraction is permitted, so one possibility is to repeatedly subtract 5 until the remaining number is less than 5, but that takes O(n), so it doesn’t satisfy the requirements. But multiplication is permitted, which means we can instead subtract powers of 5, and that is the key to a solution.
Consider the number 987. The powers of 5 less than 987 are 625, 125, 25 and 5. We subtract 625 from 987 once, leaving 362. We subtract 125 from 362 twice, leaving 112. We subtract 25 from 112 four times, leaving 12. And we subtract 5 from 12 twice, leaving 2. Since 2 is not 0, we conclude that 987 is not divisible by 5.
Our program works in two loops; the outer loop computes powers of 5, and the inner loop subtracts them:
(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)))))))
The time complexity is clearly O(5 log5 n) ≈ O(log n), as the outer loop is executed log5 n times and the inner loop is executed no more than 5 times. Here are some examples:
> (mult5? 987) #f > (mult5? 985) #t
You can run the program at https://ideone.com/LRuPUN.
(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 is very 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: