Array ( [0] => [1] => questions [2] => Basic [3] => GCD-of-3-Numbers. ) Basic | GCD of 3 Numbers. | THE INQUISITIVE

GCD of 3 Numbers.



Given three integers. You have to find the GCD of 3 given numbers.

Input Format

First line contains three integers separated by space.

Output Format

Returns the GCD of 3given numbers.

Example 1:

1 3 2	
Example 2:

2 4 8
Example 3:

3 5 7


Login to see Discussion


Note that gcd of three numbers can be found by finding gcd of first two numbers and then
finding gcd of previous gcd result and third number
Below approaches will show case for gcd of two numbers
Approach 1: Running loop upto min of both the numbers

Step-i) initialize a variable to 1
Step-ii) initialize i to 1
Step-iii) if remainder of number / i is zero assign i to variable and increment i
Step-iv) Repeat steps ii and iii till i is less than both the numbers
Step-v) return the variable

Time Complexity: O(n) where n i
Space Complexity: O(1)

Approach 2: using while loop

Step-i) if number1 is greater than number2 deduct number2 from number1
Step-ii) else deduct number1 from number2
Step-iii) repeat ii and iii till number1 is equal to number2
Step-iv) return number1

Time Complexity: O(n2-n1) where n1 and n2 are given numbers
Space Complexity: O(1)

Approach 3: Using recursion

Step-i) call the present function with parameters number2%number1 and number1 untill number1 equals to zero
Step-ii) if number1 equals to zero return number2

Time Complexity: O(logn)
Space Complexity: O(1)

Note :

Let us know if you can come up with a better approach, mail us at Your approach will be reviewed and posted with credits to you.


Login to see Solution