public class Solution {
public static int calcGCD(int n, int m){
while(m>0 && n>0){
if(m>n){
m=m%n;
}
else{
n=n%m;
}
}
if(m==0){
return n;
}
else return m;
}
}
Problem
Submissions
Hints & solutions
Discuss
GCD or HCF
Moderate
0/80
Average time to solve is 20m
Contributed by
171 upvotes
Asked in company
Problem statement
You are given two integers 'n', and 'm'.
Calculate 'gcd(n,m)', without using library functions.
The greatest common divisor (gcd) of two numbers 'n' and 'm' is the largest positive number that divides both 'n' and 'm' without leaving a remainder.
Input: 'n' = 6, 'm' = 4
Output: 2
Explanation:
Here, gcd(4,6) = 2, because 2 is the largest positive integer that divides both 4 and 6.
Detailed explanation ( Input/output format, Notes, Images )
Input format:
The first line of input contains two integers ‘n’ and 'm'.
Return an integer as described in the problem statement.
You don’t need to print anything, it has already been taken care of, just complete the given function.
Sample Input 1:
9 6
Sample Output 1:
3
Explanation of sample output 1:
gcd(6,9) is 3, as 3 is the largest positive integer that divides both 6 and 9.
Sample Input 2:
2 5
Sample Output 2:
1
Expected Time Complexity:
Try to solve this in O(log(n))
Constraints:
0 <= ‘n’ <= 10^5
Time Limit: 1 sec
Hint
Hint 1
Hint 2
Iterate through all the integers from 1 to min(n,m).
Approaches (2)
Approach 1
Approach 2
Brute Force
Approach:
We can simply iterate through all the integers from 1 to min(n,m) and check for the greatest integer that divides both ‘n’ and ‘m’.
The steps are as follows:
function calcGCD(int n, int m)
- Initialize integer ‘ans’ = 1
- for i from ‘1’ to min(n,m)
- if( n%i == 0 && m%i == 0)
- ans = i
- if( n%i == 0 && m%i == 0)
- return ans
Time Complexity
O(min(n,m)), where ‘n’ and ‘m’ are the given numbers.
We are iterating via ‘i’ from 1 to min(n,m).
Hence, the time complexity is O(min(n,m)).
Space Complexity
O(1).
We are not using any extra space.
Hence, the space complexity is O(1).
Code Solution
(100% EXP penalty)
GCD or HCF
All tags
Sort by
Interview problems
GCD or HCF
int calcGCD(int n, int m){
for(int i = min(n,m); i>0; i--){
if(n%i==0 && m%i==0){
return i;
}
}
return 1;
}
17 views
0 replies
0 upvotes
Interview problems
C++ Runtime graph( beats 100% and runtime 32ms) and memory graph(beats 91.19% and memory 11681 kB)
int calcGCD(int n, int m){
// Write your code here.
while (n>0 && m>0){
if (n>m){
n=n%m;
}
else{
m=m%n;
}
}
if (n==0) return m;
return n;
}
40 views
0 replies
0 upvotes
Interview problems
beats 100% c++ code
int calcGCD(int n, int m){
while (n > 0 && m > 0) {
if (n > m)
n = n % m;
else
m = m % n;
}
if (n == 0) return m;
return n;
}
62 views
0 replies
0 upvotes
Interview problems
using java. Euclidean algorithmused
public class Solution {
public static int calcGCD(int n, int m){
// Write your code here.
int a=0;
int b=0;
if(n>m){
a=n;
b=m;
}
else{
a=m;
b=n;
}
while(true){
int digit=a%b;
if(digit==0){
return b;
}
a=b;
b=digit;
}
}
}
37 views
0 replies
0 upvotes
Interview problems
Code of Time Complexity O(log(n)).
public class Solution {
public static int calcGCD(int n, int m){
// Write your code here.
if(m>n){
int temp = m;
m=n;
n=temp;
}
int r;
for(;;){
if(n%m==0){
break;
}
else{
r=n%m;
n=m;
m=r;
}
}
return m;
}
}
32 views
0 replies
0 upvotes
Interview problems
java Solution
public class Solution {
public static int calcGCD(int n, int m){
int gcd=2, count=1;
if(n==m)
{
return n;
}
else{
while(gcd<n || gcd<m)
{
if(n%gcd==0 && m%gcd==0)
{
count=gcd;
}
gcd=gcd+1;
}
return count;
}
}
}
47 views
0 replies
0 upvotes
Interview problems
why is the timecomplexity for the following code high
int calcGCD(int n, int m){
while(n!=m)
{
if(n>m)
n=n-m;
else
m=m-n;
}
return m;
}
76 views
0 replies
0 upvotes
Interview problems
Euclidean Algorithm Java Optimal code
public class Solution {
public static int calcGCD(int n, int m){
// Write your code here.
while(n>0 && m > 0){
if(n>m) n = n%m;
else m = m% n;
}
if(n==0) return m;
else return n ;
}
}
93 views
0 replies
0 upvotes
Interview problems
hcf using recursion
int calcGCD(int n, int m){
// Write your code here.
int rem;
rem=n%m;
if(rem==0)
return m;
else
return calcGCD(m,rem );
}
108 views
0 replies
0 upvotes
1
2
3
4
C++ (g++ 5.4)
Console