GCD/HCF and LCM

HCF (24, 36)

Brute Force Approach 1: Verify for loop from i=0 to 24 to get HFC

Brute Force Approach 2(better than above): Verify for loop from i=24 to 0 to get HFC, here you'll get HCF more faster

Euclidean Theorm: gcd (a, b) = gcd (b, a % b)

HCF * LCM = a * b

import java.util.Scanner;

public class GcdLcm {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();

        System.out.println("HCF = " + gcdBruteForce(a, b));

        int hcf = gcdIterative(a, b);


        // Calculate and output LCM using the formula: LCM(a, b) = |a * b| / GCD(a, b)
        // Time Complexity: O(1) for multiplication and division
        System.out.println("LCM = " + (a * b / hcf));

    }

    /*
        Time Complexity: O(min(a, b))
        (Slower than Euclidean, especially for large numbers)
        Space Complexity: O(1)
        */
    public static int gcdBruteForce(int a, int b) {
        int gcd = 1;               // TC: O(1), SC: O(1)
        int min = Math.min(a, b); // TC: O(1), SC: O(1)

        for (int i = 1; i <= min; i++) {    // TC: O(min(a, b))
            if (a % i == 0 && b % i == 0) { // TC: O(1) per iteration
                gcd = i;                    // TC: O(1)
            }
        }
        return gcd;               // TC: O(1)
    }

    /*
     * Time Complexity (TC):
     *
     * Best case: O(1)
     * - If num2 is 0 at the start, the loop doesn't run, and we only perform a few calculations.
     *
     * Average case: O(log(min(num1, num2)))
     * - The Euclidean algorithm is efficient and runs in logarithmic time relative to the smaller of the two numbers.
     *
     * Worst case: O(log(min(num1, num2)))
     * - The worst-case scenario also occurs when the algorithm takes the maximum number of iterations to compute the GCD.
     *
     * Space Complexity (SC):
     *
     * SC: O(1)
     * - The space used is constant; we only utilize a few integer variables (num1, num2, o_num1, o_num2, temp) without requiring additional storage.
     */
    public static int gcdIterative(int a, int b) {

        while (b != 0) {           // TC: O(log(min(a, b))) — loop runs log times as b decreases
            int temp = b;          // TC: O(1), SC: O(1)
            b = a % b;             // TC: O(1), SC: O(1)
            a = temp;              // TC: O(1), SC: O(1)
        }
        return a;                  // TC: O(1), SC: O(1)
    }


}