Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation
      • 19
        BFS

    • Greatest common divisor (GCD) with subtraction

    Given two positive integers a and b, you are asked to calculate the greatest common divisor of those. Yet, this time those numbers are way larger. So, finding all the divisors of each of those and then finding the largest common one won’t help. We should optimize the algorithm.
    Let’s take the case where a > b. If we think about a common divisor d, both a and b are divisible by d. Meaning that:
    where x and y are some integers. If we subtract b from a, we’ll get:
     
    So, d is the divisor of both a and b, and as both x and y are integers ⇒ x-y is also an integer. Therefore as a-b = d(x-y), d should be a divisor of b - a. This observation is really helpful and can optimize the number of steps we perform in our program to find the GCD.
    If the greatest common divisor d divides both a, b, and a-b, then we can find d by finding the greatest common divisor of b and a-b instead of a which was a larger number. We can repeat this process until either a or b turns 0 (in which case the nonzero element is the greatest divisor):
    a, b = int(input()), int(input())
while a > 0 and b > 0:  # In case a or b is 0 => the other one is the GCD
	if b > a:             # Let's always keep a >= b
		a, b = b, a         # Swap the numbers
	a, b = a - b, b       # gcd of (a, b) is the same as gcd of (a, b - a)

d = b if a == 0 else a  # if a is 0 => b is GCD, if b is 0 => a is GCD
print('gcd:', d)
    Let’s run several simulations of the algorithm:
    a = 8, b = 12
    1. b > a ⇒ swap ⇒ a = 12, b = 8 a = 12 - 8 = 4, b = 8
    1. b > a ⇒ swap ⇒ a = 8, b = 4 a = 8 - 4 = 4, b = 4
    1. a = 4 - 4 = 0, b = 4
    1. break ⇒ GCD = 4
    a = 54, b = 24
    1. a = 54 - 24 = 30, b = 24
    1. a = 30 - 24 = 6, b = 24
    1. b > a ⇒ swap ⇒ a = 24, b = 6 a = 24 - 6 = 18, b = 6
    1. a = 18 - 6 = 12, b = 6
    1. a = 12 - 6 = 6, b = 6
    1. a = 6 - 6 = 0, b = 6
    1. break ⇒ GCD = 6
    a = 17, b = 16
    1. a = 17 - 16 = 1, b = 16
    1. b > a ⇒ swap ⇒ a = 16, b = 1 a = 16 - 1 = 15, b = 1
    1. a = 14, b = 1
    1. a = 13, b = 1
    1. a = 12, b = 1
    1. …
    1. …
    1. a = 0, b = 1
    1. break ⇒ GCD = 1

    Input

    The only line of the input contains two integers a and b (0 ≤ a, b ≤ ).

    Output

    The program should print the greatest common divisor of a and b.

    Examples

    Input
    Output
    8 12
    4
    54 24
    6
    17 16
    1

    Constraints

    Time limit: 1 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

    To check your solution you need to sign in
    Sign in to continue