Greatest Common Divisor InterviewBit Solution
Problem: Greatest Common Divisor
Problem Description:
Given 2 non-negative integers m and n, find gcd(m, n)
GCD of 2 integers m and n is defined as the greatest integer g such that g is a divisor of both m and n. Both m and n fit in a 32 bit signed integer.
Example
m : 6
n : 9
GCD(m, n) : 3
Approach
We need to find the greatest common divisor. For that, we can use the famous Euclidean Algorithm.
Time & Space Complexity
Time Complexity: O(logN)
Space Complexity: O(1)
Solution:
Code in C++
תגובות