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.

Advertisements

Pages: 1 2

29 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+$_[0],$_[1]); }
    
    sub mod {
      $_[2]||=$_[1];
      $_[0] = mod( @_[0,1], $_[1]*$_[2] ) if $_[1] >= $_[1]*$_[2];
      $_[0] -= $_[1] while $_[0] >= $_[2];
      return $_[0]
    }
    
  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=~/[05]$/}
    [sourcecode]

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

    sub mult5{shift=~/[05]$/}
    
  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 = [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) ])
    
  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 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
        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[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:

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

    Example:

    $ ./mult5 987
    0
      
    $ ./mult5 985
    1
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: