Modulo

Coding Skill Exercise #2

Modulo

Compute a % b without using % operator.

Knowledge Gap Finder

If you are unable to code the solution, answer the following questions and reply to this email to get customized lesson.

Was the problem statement clear to you when you read it? What did you think of doing first? Were you reminded of a construct in general or a general structure of solution that you thought would be useful? Have you previously seen problems that resemble this one? Did you feel stuck at any point while working on this problem? What did you choose as your test case? Do you think you’ve covered all possible scenarios with your tests? What program design techniques did you apply to solve this problem? Are there any constructs of the programming language that you find difficult or confusing to use? What issues make programming constructs difficult to use? For example, the keyword used, the syntax, the examples, the documentation for the construct, etc.

Feel free to forward this email to your friends so they can subscribe here https://codingskill.biz/.

layout: post title: Modulo Operation excerpt: This covers the basics of modulo operation and the problem based on it. tags: linear-scan modulo-operator for-loop while-loop reduction-of-return-value divisible-check reducing-value-by-substraction counter chained-conditional accumulator

Modulus operator is an operator, denoted with a percent sign (%) in Ruby. It works on integers and returns the remainder when one number is divided by another.

The simplest thing that can be done with the modulo operator is checking if a number is divisble by another number.

1
2
3

def divisible?(number, divisor)
  number % divisor == 0
end

Implement Modulo Operation

To get a better understanding of the modulo operation, implement the % operator without using the language builtin modulus operator. The implementation:

1
2
3
4
5
6
7
8
9

def modulus(a, b)
  remainder = a
  
  while remainder > 0 && remainder >= b
    remainder -= b 
  end
  
  remainder
end

Using formula to implement modulo operation:

1
2
3
4

def modulus(a, b)
  ans = a / b
  r = a - b * ans
end

The modulo is the remainder after dividing one number by another. Let a = 19, b = 5. 19 cannot be divided exactly by 5. The closest we can get (without going over) is: 3 x 5 = 15, which is 4 less than 19. So the answer of 19 ÷ 5 is: 19 ÷ 5 = 3 R 4 Check it by multiplying: 5 × 3 + 4 = 19, r = a - b x ans

Refer mathisfun website for detailed explanation with illustrations.

Multiples of a Number

Write a function that takes a parameter n and returns the sum of numbers that are multiples of three or five, e.g. 3, 5, 6, 9, 10, 12, 15.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def sum(n)
  result = 0

  for i in (1..n)
    if (i % 3 == 0) || (i % 5 == 0)
      result += i
    end
  end
  
  result
end

Fizz Buzz problem can be solved based on understanding of modulus operator. One of the building blocks in Fizz Buzz is the chained conditional. Chained conditional is a conditional statement with a series of alternative branches.

Sometimes there are more than two possibilities and it requires more than two branches. One way to express this kind of computation is called chained conditional.

Odd and Even Number

Write a method to check if a given number is even without using language builtin methods.

Since the modulo operator returns the remainder of division, we can use it in the implementation:

1
2
3
4
5

def even?(n)
  n % 2 == 0
end

p even?(4)

We can reuse the divisible method to make this method readable:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def divisible?(number, divisor)
  number % divisor == 0
end

def even?(number)
  divisible?(number, 2)
end

p even?(3)
p even?(2)

You can now write a method to check if a given number is odd without using language builtin methods. Modify the solution for even to implement the odd? method.

Problems that uses modulo operator as a basic building block:

• [Extract RightMost Digit]({% post_url 2021-02-15-subtract-product-and-sum-of-digits %})
• [Cycle Through a Set of Values ]({% post_url 2021-05-07-excel-sheet-encode %})

Some problems require you to combine the modulo with division to solve the problem.

Primality Test

Prime numbers are the positive integers having only two factors, 1 and the integer itself. For example, factors of 3 are only 1 and 3, totally two. Hence, 3 is a prime number. 1 is neither prime nor composite.

Some prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def prime?(n)
  if n < 2
    return false
  end
  
  i = 2
  while i * i <= n
    if (n % i == 0)
      return false
    end
    i += 1  
  end
  
  return true 
end

p prime?(97)

Equivalence Relation

Modulus operation can be used to define an equivalence relation. For the set of integers, use the modulus function to define a binary relation such that two numbers x and y are in the relation if and only if:

x mod m = y mod m

Thus, for m = 4,〈1,5〉is in the relation because 1 mod 4 = 5 mod 4.

1
2
3
4

001 > 5 % 4
 => 1 
002 > 1 % 4
 => 1 

We see that modulus used in this way defines an equivalence relation on the integers and this relation can be used to partition the integers into m equivalence classes.

Building Blocks

• Linear Scan
• Modulo Operator
• for Loop
• while Loop
• Reduction of Return Value
• Divisible Check
• Reducing Value by Substraction
• Accumulator