top of page

Looking to master object-oriented and system design for tech interviews or career growth?

  • Improve your system design and machine coding skills.

  • Study with our helpful resources.

  • Prepare for technical interviews and advance your career.

**We're in beta mode and would love to hear your feedback.

Greatest Common Divisor InterviewBit Solution


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++


תגובות


bottom of page