LCM and GCD Geeks For Geeks

 Problem Link:

https://practice.geeksforgeeks.org/problems/lcm-and-gcd4516/1/

Solution:

 class Solution {

    static Long fun(Long a, Long b){

        if(b==0){

            return a;

        }

        else{

            return fun(b,a%b);

        }

    } 

    static Long[] lcmAndGcd(Long a , Long b) { 

        Long c=fun(a,b);

        Long arr[]=new Long[2];

        Long d=(a*b)/c;

          arr[0]=d;

          arr[1]=c;

        // System.out.println(arr[0]+" "+arr[1]);

        return arr;

    }

};

TIME:O(log(min(a,b)))[GFG Time:0.1/1.5]

SPACE:O(1)[Array arr of size 2 is created.]

AUXILLARY SPACE:O(Logn)[Log n calls are made till the parameter b becomes 0 and at any moment maximum logn calls can be stored in a stack.]

Total Test Cases:102

Approach:

For HCF:

Here we will use recursion. Every time we will pass two parameters a and b (given numbers) but the concept use will be modular division, ie a%b as the second parameter.

This will reduce the value of second parameter continously till it becomes 0.Once it attains value 0 we will return first paramater value at that time.

eg for a=12 b=15

fun(12,15) -> fun(15,12)->fun(12,3)->fun(3,0)-> return 3;

eg for a=15 b=12

fun(15,12)->fun(12,3)->fun(3,0)->return 3;

In case 1, a total of 4 calls is made while in case 2 only 3 calls are made. One extra call made is because a<b, which get swapped after the first call, as 12%15=12 ie for numbers less than 15 same number will be returned while for numbers greater than 15 modulo will be used.

For LCM:

We can clearly observe that the maximum value of lcm of any two numbers can be their product if they are coprime, while if they have factors in common then lcm will not be direct multiplication.

It will be multiplication/HCF.

"Thanks For Reading.😇"

"Share Further To Increase Knowledge Treasure.😊"