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

First line contains three integers separated by space.

Returns the GCD of 3given numbers.

Example 1:

Input

1 3 2

Output

1

Example 2:

Input

2 4 8

Output

2

Example 3:

Input

3 5 7

Output

1

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 support@theinquisitive.in Your approach will be reviewed and posted with credits to you.

Login to see Solution