Backend interview prep

Start Learning

GCD HCF

Java coding interview problem for Number Logic: GCD HCF.

Finding the Greatest Common Divisor (GCD) or Highest Common Factor (HCF) of two numbers is one of the most common Java coding interview questions.

This problem helps interviewers evaluate your understanding of:

  • Loops
  • Conditional statements
  • Mathematical concepts
  • Optimization techniques
  • Problem-solving skills

GCD is widely used in mathematics, cryptography, fractions, number theory, and competitive programming.

What is GCD (HCF)?

The Greatest Common Divisor (GCD) is the largest positive integer that divides two or more numbers without leaving a remainder.

It is also called

  • Highest Common Factor (HCF)
  • Greatest Common Factor (GCF)

All three terms refer to the same concept.

Example 1

Find the GCD of

12 and 18

Factors of 12

1

2

3

4

6

12

Factors of 18

1

2

3

6

9

18

Common Factors

1

2

3

6

Largest Common Factor

6

Therefore

GCD(12,18) = 6

Example 2

Find the GCD of

20 and 30

Factors of 20

1

2

4

5

10

20

Factors of 30

1

2

3

5

6

10

15

30

Common Factors

1

2

5

10

Largest

10

Therefore

GCD(20,30) = 10

Example 3

Input

7

13

Factors

7 → 1,7

13 → 1,13

Only Common Factor

1

Output

1

These numbers are called co-prime numbers.

Real Interview Question

Write a Java program to find the Greatest Common Divisor (GCD) or Highest Common Factor (HCF) of two numbers.

Understanding the Logic

Suppose

number1 = 24

number2 = 36

The GCD cannot be greater than the smaller number.

So,

minimum = 24

Check every number from

1

to

24

If a number divides both numbers perfectly,

store it as the current GCD.

Continue until all numbers are checked.

The last stored value is the answer.

Visual Representation

Input

24

36

Check

1

✓

2

✓

3

✓

4

✓

5

✗

6

✓

...

12

✓

...

24

✗

Largest valid divisor

12

Output

GCD = 12

Brute Force Approach

The simplest approach is

  • Find the smaller number.
  • Check every number from 1 to the smaller number.
  • If the number divides both numbers, store it.
  • Continue until the end.
  • Print the stored value.

Algorithm

Step 1

Read two numbers.

Step 2

Find the minimum.

min = Math.min(number1, number2);

Step 3

Initialize

gcd = 1;

Step 4

Loop from

1

to

min

Step 5

Check

number1 % i == 0

&&

number2 % i == 0

Step 6

Update

gcd = i;

Step 7

Continue until the loop ends.

Step 8

Print

gcd

Dry Run

Input

18

24

Minimum

18
Iteration Divides 18? Divides 24? Current GCD
1 Yes Yes 1
2 Yes Yes 2
3 Yes Yes 3
4 No Yes 3
5 No No 3
6 Yes Yes 6
7 No No 6
8 No Yes 6
9 Yes No 6
10-18 No Mixed 6

Output

6

Another Dry Run

Input

25

40

Minimum

25

Common divisors

1

5

Largest

5

Output

5

Approach 1 — Using Iteration (Brute Force)

This is the easiest solution and is ideal for beginners.

Complete Java Program

public class GCDExample {

    public static void main(String[] args) {

        int number1 = 24;
        int number2 = 36;

        int min = Math.min(number1, number2);

        int gcd = 1;

        for (int i = 1; i <= min; i++) {

            if (number1 % i == 0 && number2 % i == 0) {

                gcd = i;

            }

        }

        System.out.println("GCD = " + gcd);

    }

}

Output

GCD = 12

Step-by-Step Code Explanation

Step 1

Declare the input numbers.

int number1 = 24;
int number2 = 36;

Current values

24

36

Step 2

Find the smaller number.

int min = Math.min(number1, number2);

Result

24

The GCD cannot be greater than the smaller number.

Step 3

Initialize the GCD.

int gcd = 1;

Initially

gcd = 1

Step 4

Loop through all possible divisors.

for (int i = 1; i <= min; i++)

The loop checks every possible divisor.

Step 5

Check whether the current number divides both numbers.

if (number1 % i == 0 &&
    number2 % i == 0)

If true,

update

gcd = i;

Since the loop moves from smaller to larger values,

the final stored divisor is the greatest one.

Step 6

Print the answer.

System.out.println("GCD = " + gcd);

Output

GCD = 12

Example Execution

Input

48

60

Common Factors

1

2

3

4

6

12

Largest

12

Output

GCD = 12

Input

9

27

Common Factors

1

3

9

Largest

9

Output

GCD = 9

Why Does This Work?

The algorithm checks every possible divisor from 1 up to the smaller number.

Whenever a number divides both inputs without leaving a remainder, it is a common divisor.

Since the loop proceeds in increasing order, the last common divisor found is guaranteed to be the Greatest Common Divisor (GCD).

Advantages of This Approach

  • Very easy to understand.
  • Excellent for beginners.
  • Simple implementation using loops.
  • Works for all positive integers.
  • Frequently asked as a basic interview question.

Drawbacks

Although this solution is simple, it is not the most efficient for large numbers because it checks every possible divisor.

Interviewers often ask follow-up questions such as:

  • Can you solve it without checking every number?
  • Can you optimize the solution using the Euclidean Algorithm?
  • Why is the Euclidean Algorithm faster?
  • Can you implement it using recursion?
  • What is the time complexity of both approaches?

In the next part, we'll cover:

  • Euclidean Algorithm (Optimized Approach)
  • Recursive Solution
  • Reusable Method
  • Time and Space Complexity
  • Comparison of All Approaches
  • Common Interview Mistakes
  • Frequently Asked Interview Questions
  • Related Coding Problems
  • Key Takeaways
  • Interview Tips

Approach 2 — Using Euclidean Algorithm (Optimized)

The Euclidean Algorithm is the most efficient and widely used method for finding the Greatest Common Divisor (GCD).

Instead of checking every possible divisor, it repeatedly replaces the larger number with the remainder until the remainder becomes 0.

The last non-zero divisor is the GCD.

Mathematical Formula

The Euclidean Algorithm is based on the following property.

GCD(a, b)

=

GCD(b, a % b)

Continue until

b = 0

Then

GCD = a

Understanding the Logic

Suppose

a = 48

b = 18

Step 1

48 % 18 = 12

Now

a = 18

b = 12

Step 2

18 % 12 = 6

Now

a = 12

b = 6

Step 3

12 % 6 = 0

Now

a = 6

b = 0

Stop.

Output

GCD = 6

Visual Representation

48,18

↓

48 % 18 = 12

↓

18,12

↓

18 % 12 = 6

↓

12,6

↓

12 % 6 = 0

↓

6,0

↓

Answer = 6

Algorithm

Step 1

Read two numbers.

Step 2

Repeat while

number2 != 0

Step 3

Store

remainder = number1 % number2;

Step 4

Update

number1 = number2;
number2 = remainder;

Step 5

Repeat until

number2 = 0

Step 6

Return

number1

Dry Run

Input

36

24
Iteration Number1 Number2 Remainder
1 36 24 12
2 24 12 0

Output

12

Another Dry Run

Input

81

54
Iteration Number1 Number2 Remainder
1 81 54 27
2 54 27 0

Output

27

Java Program

public class GCDEuclidean {

    public static void main(String[] args) {

        int number1 = 48;
        int number2 = 18;

        while (number2 != 0) {

            int remainder = number1 % number2;

            number1 = number2;

            number2 = remainder;

        }

        System.out.println("GCD = " + number1);

    }

}

Output

GCD = 6

Approach 3 — Using Recursion

The Euclidean Algorithm can also be implemented recursively.

Recursive Formula

GCD(a,b)

=

GCD(b,a%b)

Base Condition

If b == 0

Return a

Java Program

public class GCDRecursion {

    static int gcd(int a, int b) {

        if (b == 0) {

            return a;

        }

        return gcd(b, a % b);

    }

    public static void main(String[] args) {

        int number1 = 48;
        int number2 = 18;

        System.out.println("GCD = " + gcd(number1, number2));

    }

}

Output

GCD = 6

Approach 4 — Using a Reusable Method

Reusable methods improve

  • Code readability
  • Code reuse
  • Unit testing
  • Maintainability

Java Program

public class GCDMethod {

    static int gcd(int a, int b) {

        while (b != 0) {

            int remainder = a % b;

            a = b;

            b = remainder;

        }

        return a;

    }

    public static void main(String[] args) {

        System.out.println(gcd(84, 30));

    }

}

Output

6

Time Complexity

Brute Force

Operation Complexity
Time O(min(a,b))
Space O(1)

Euclidean Algorithm

Operation Complexity
Time O(log(min(a,b)))
Space O(1)

Recursive Euclidean Algorithm

Operation Complexity
Time O(log(min(a,b)))
Space O(log(min(a,b)))

The recursive solution requires additional stack memory.

Comparison of All Approaches

Approach Time Space Recommended
Brute Force O(min(n)) O(1) Good for Beginners
Euclidean Algorithm O(log n) O(1) ✅ Best for Interviews
Recursive Euclidean O(log n) O(log n) Elegant Solution
Reusable Method O(log n) O(1) Production Ready

Common Mistakes

Mistake 1

Checking divisibility up to the larger number.

Wrong

for(int i = 1; i <= number1; i++)

Always iterate only up to the smaller number.

Mistake 2

Using division instead of modulus.

Wrong

number1 / number2

Correct

number1 % number2

The Euclidean Algorithm depends on the remainder, not the quotient.

Mistake 3

Incorrect loop condition.

Wrong

while(number1 != 0)

Correct

while(number2 != 0)

Mistake 4

Forgetting to update both variables.

Wrong

number2 = number1 % number2;

Correct

int remainder = number1 % number2;

number1 = number2;

number2 = remainder;

Mistake 5

Missing the recursion base condition.

Wrong

return gcd(b, a % b);

Correct

if (b == 0)

return a;

Interview Follow-up Questions

Q1. Find the LCM using GCD.

Q2. Explain why the Euclidean Algorithm works.

Q3. Which approach is faster?

Q4. Find the GCD of an array.

Q5. Find the GCD of three numbers.

Q6. Find whether two numbers are co-prime.

Q7. Implement GCD recursively.

Q8. Implement GCD iteratively.

Q9. Compare recursion and iteration.

Q10. What is the relationship between GCD and LCM?

Related Coding Problems

  • LCM of Two Numbers
  • Prime Number
  • Co-prime Numbers
  • Decimal to Binary
  • Fibonacci Series
  • Factorial
  • Power of a Number
  • Armstrong Number

Key Takeaways

  • GCD, HCF, and GCF represent the same mathematical concept.
  • The brute-force solution checks every possible divisor.
  • The Euclidean Algorithm repeatedly computes the remainder until it becomes zero.
  • The last non-zero divisor is the GCD.
  • The Euclidean Algorithm is the most efficient solution and is commonly expected in coding interviews.
  • The iterative Euclidean solution runs in O(log n) time with O(1) extra space.

Interview Tip

If an interviewer asks:

"Write a Java program to find the GCD (HCF) of two numbers."

Start with the Euclidean Algorithm, as it is the industry-standard solution. Explain the mathematical property:

GCD(a, b) = GCD(b, a % b)

Discuss why it is significantly faster than the brute-force approach and mention its O(log n) time complexity. If time permits, also demonstrate the recursive implementation and explain the relationship between GCD and LCM:

LCM(a, b) = (a × b) / GCD(a, b)

Knowing both approaches and their trade-offs demonstrates a strong understanding of algorithms and mathematical problem-solving in Java.