In the subtractive Euclidean algorithm, instead of repeatedly dividing and taking the remainder, we continually subtract the smaller number from the larger number until they become equal. This equal number is the GCD.

Approach

Here is the approach:

  1. Subtract the smaller number from the larger number repeatedly.
  2. Continue until both numbers become equal.
  3. The result is the GCD.

Solutions

Method 1- Recursive

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public class SubtractiveEuclideanGCD {
    
    public int gcd(int a, int b) {
        // Handle base cases for 0 and equality
        if (a == 0) {
            return b;
        }

        if (b == 0) {
            return a;
        }

        if (a == b) {
            return a;
        }

        // Use the subtractive Euclidean algorithm
        if (a > b) {
            return gcd(a - b, b);
        } else {
            return gcd(a, b - a);
        }
    }

    public static void main(String[] args) {
        SubtractiveEuclideanGCD solution = new SubtractiveEuclideanGCD();
        System.out.println(solution.gcd(56, 98));  // Output: 14
        System.out.println(solution.gcd(48, 18));  // Output: 6
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class SubtractiveEuclideanGCD:
    
    def gcd(self, a, b):
        # Handle base cases for 0 and equality
        if a == 0:
            return b
        if b == 0:
            return a
        if a == b:
            return a
        
        # Use the subtractive Euclidean algorithm
        if a > b:
            return self.gcd(a - b, b)
        else:
            return self.gcd(a, b - a)

# Example usage
solution = SubtractiveEuclideanGCD()
print(solution.gcd(56, 98))  # Output: 14
print(solution.gcd(48, 18))  # Output: 6

Complexity

  • ⏰ Time complexity: O(max(a, b)) in the worst case because it involves linear subtraction.
  • 🧺 Space complexity: O(max(a, b)) due to the recursive calls on the stack, as each call reduces only one of the numbers slightly.

Method 2 - Iterative

Code

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

public class SubtractiveGCD {
    public int gcd(int a, int b) {
        while (a != b) {
            if (a > b) {
                a -= b;
            } else {
                b -= a;
            }
        }
        return a;
    }

    public static void main(String[] args) {
        SubtractiveGCD solution = new SubtractiveGCD();
        System.out.println(solution.gcd(56, 98));  // Output: 14
        System.out.println(solution.gcd(48, 18));  // Output: 6
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class SubtractiveGCD:
    def gcd(self, a, b):
        while a != b:
            if a > b:
                a -= b
            else:
                b -= a
        return a

# Example usage
sg = SubtractiveGCD()
print(sg.gcd(56, 98))  # Output: 14
print(sg.gcd(48, 18))  # Output: 6

Complexity

  • ⏰ Time complexity: O(max(a, b)) in the worst case because it involves linear subtraction.
  • 🧺 Space complexity: O(1) as it uses constant space.