GCD (HCF) and LCM

Greatest Common Divisor (GCD)

The basic approach iterates from 1 to the smaller of the two numbers and continuously updates the greatest common divisor whenever a common factor is found.

int gcd = 1;

for (int i = 1; i <= Math.min(a, b); i++) {
    if (a % i == 0 && b % i == 0) {
        gcd = i;
    }
}

Logic

  • Traverse from 1 to the smaller number.
  • Check whether both numbers are divisible by the current value.
  • Store the largest common divisor.

Optimized Approach

Use the Euclidean Algorithm.

while (b != 0) {
    int temp = b;
    b = a % b;
    a = temp;
}

The remaining value of a becomes the GCD.

Advertisement

Least Common Multiple (LCM)

Calculate the LCM using:

LCM = (a × b) / GCD

Sum of Digits & Smallest/Largest Digit

Sum of Digits

Extract each digit and accumulate the total.

sum += num % 10;
num = num / 10;

Repeat until the number becomes zero.

Smallest & Largest Digit

public class SmallestLargestDigit {

    public static void main(String[] args) {

        int num = 52749;

        int smallest = 9;
        int largest = 0;

        while (num > 0) {

            int digit = num % 10;

            if (digit > largest)
                largest = digit;

            if (digit < smallest)
                smallest = digit;

            num = num / 10;
        }

        System.out.println("Smallest: " + smallest +
                ", Largest: " + largest);
    }
}

Logic

Initialize:

  • Smallest = 9
  • Largest = 0

Traverse every digit and update both values accordingly.

Reverse a Number Using Recursion

public class ReverseNumberRecursion {

    static int rev = 0;

    static void reverse(int num) {

        if (num == 0)
            return;

        int digit = num % 10;

        rev = rev * 10 + digit;

        reverse(num / 10);
    }

    public static void main(String[] args) {

        reverse(1234);

        System.out.println("Reversed: " + rev);
    }
}

Logic

The recursive solution follows the same digit extraction pattern.

  • Extract the last digit.
  • Append it to the reversed number.
  • Recursively process the remaining digits.
  • Stop when the number becomes 0.

For 1234, the reversed number is built as:

4 → 43 → 432 → 4321

Print numbers without using loops.

Ascending Order

  • Recursively call the function first.
  • Print while returning from recursion.

Descending Order

  • Print the current value.
  • Then recursively call the next value.

The recursion terminates when the base condition is reached.

Decimal to Binary & Binary to Decimal

Decimal to Binary

public class DecimalToBinary {

    public static void main(String[] args) {

        int num = 13;

        int[] binary = new int[40];

        int index = 0;

        while (num > 0) {

            binary[index++] = num % 2;

            num = num / 2;
        }

        // print binary[] from index-1 down to 0
    }
}

Logic

  • Divide the decimal number by 2.
  • Store each remainder.
  • Print the remainders in reverse order.

Example:

13 → 1101

Binary to Decimal

Convert binary to decimal by multiplying each bit with its positional power of 2 and summing the results.

Neon Number & Fibonacci

Neon Number

A Neon number is a number whose square's digit sum equals the original number.

Example:

9² = 81
8 + 1 = 9

Fibonacci Series

Generate the Fibonacci sequence beginning with:

0, 1

Each subsequent number is obtained by adding the previous two numbers.

Frequently Asked Questions

How do you find the GCD of two numbers?

Use either:

  • A loop from 1 to the smaller number.
  • The Euclidean Algorithm for an optimized solution.

Once the GCD is known:

LCM = (a × b) / GCD

How do you reverse a number using recursion?

Extract the last digit, append it to the reversed number, recursively process the remaining digits, and terminate when the number becomes zero.

How do you convert a decimal number to binary?

Repeatedly divide the decimal number by 2, store the remainders, and print them in reverse order.

How do you find the smallest and largest digit in a number?

Initialize:

  • Smallest = 9
  • Largest = 0

Extract every digit using % 10 and update both values during traversal.

What is a Neon number?

A Neon number is a number whose square's digit sum equals the original number.

Example:

9² = 81
8 + 1 = 9