This article will deep dive and discuss how to find gcd of two numbers. Finding a GCD of two numbers will help in developing the basic logical skills and coding skills that will enhance your career. Practice regularly for coding questions like hot to find gcd of two numbers will be a good habit and will strengthen you for the interviews of tech Organizations. Many complicated questions are solved using GCD of two numbers. GCD of two numbers are the basics if you just entered for solving coding problems or in your coding career. Let’s get back to our topic, we will see and solve the problem to find gcd of two numbers.
How to Find GCD of Two Numbers:
For given two large numbers M and N, find their gcd(M,N).
GCD(M,N) is the largest number possible which divides both.
Finding a GCD of two numbers is not a complicated task. From basic mathematics you can solve how to find GCD of two numbers.
See original problem statement here
Test Case:
Input: 15 130
Output: 5
Explanation:
5 divides 15 and 130 both completely and there exists no number greater than 5 which divides both of them completely.
Solving Approach How To Find GCD Of Two Numbers :
- For provided numbers, we know N is of size less than or equal to 100, so we would need to store this number in a string.
- We know we get the remainder less than N always if we divide any number by N.
- To get the remainder by dividing a number stored String by Number, we calculate the remainder digit by digit. We update the remainder at every digit until all strings are iterated.
- In each iteration, we take the digit and make it greater than our current remainder by multiplying it by 10 and adding it to the digit, now we take the mod of digit by N and store it as our current remainder. After the whole string is iterated, we get our remainder.
- After we divide M by N and extract it’s remainder, now both of them are in the Long Integer range, and we can carry with us our Long Division Method for getting gcd(M,N) where M is our new smaller number.
- Long Division Method: We repeatedly store remainder i.e (Larger number % Smaller number) and update Larger number by Smaller number until smaller number completely divides the larger number. Last Smaller Number after all steps, is our gcd.
Example:
We’ll be given two numbers out of which one is a string and one is a long number. Hence we find the remainder of string number and long number.
We can dry run the above mentioned technique,let’s say given numbers are 143254 and 3, so first we convert 143254 to a long number which will be 143254 % 3. We take mod=0, which will store our final value, So,
As we have got our values in integer form, we can now use the long division method, to find out the gcd of both numbers that is gcd(n,mod).
Let’s take 25 and 135 for example, we find gcd of both using the Long Division Method.
As soon as our remainder becomes 0, dividend is our gcd(a,b). Let’s see all the solutions for finding gcd of two numbers in (c, java, Python).
Solutions:
#include <stdio.h>
#include<string.h>
long long modBigNumber(char num[], long long m)
{
long long mod = 0;
for (int i = 0; i < strlen(num); i++) {
int digit = num[i] - '0';
mod = mod * 10 + digit;
mod = mod % m;
}
return mod;
}
int main()
{
int test;
scanf("%d",&test);
while(test--){
long long small;
long long largeF;
char large[2001];
scanf("%lld%s",&small,large);
largeF = modBigNumber(large,small);
if(largeF==0){
printf("%lld\n",small);
}
else{
int temp = small;
small = largeF;
largeF = temp;
while(1){
if(largeF%small==0){
printf("%lld\n",small);
break;
}
int temp = small;
small = largeF%small;
largeF = temp;
}
}
}
}
#include <bits/stdc++.h>
using namespace std;
long long modBigNumber(string num, long long m)
{
long long mod = 0;
for (int i = 0; i < num.size(); i++) {
int digit = num[i] - '0';
mod = mod * 10 + digit;
mod = mod % m;
}
return mod;
}
int main()
{
int test;
cin>>test;
while(test--){
long long small;
long long largeF;
string large;
cin>>small>>large;
largeF = modBigNumber(large,small);
if(largeF==0){
cout<<small<<endl;
}
else{
int temp = small;
small = largeF;
largeF = temp;
while(true){
if(largeF%small==0){
cout<<small<<endl;
break;
}
int temp = small;
small = largeF%small;
largeF = temp;
}
}
}
}
import java.util.*;
import java.io.*;
public class Main {
static long modBigNumber(String num, long m){
long mod = 0;
for (int i = 0; i < num.length(); i++) {
int digit = num.charAt(i) - '0';
mod = mod * 10 + digit;
mod = mod % m;
}
return mod;
}
public static void main(String args[]) throws IOException {
Scanner sc = new Scanner(System.in);
int test = sc.nextInt();
while(test!=0){
long small = sc.nextLong();
long largeF;
String large = sc.next();
largeF = modBigNumber(large,small);
if(largeF==0){
System.out.println(small);
}
else{
long temp = small;
small = largeF;
largeF = temp;
while(true){
if(largeF%small==0){
System.out.println(small);
break;
}
temp = small;
small = largeF%small;
largeF = temp;
}
}
test--;
}
}
}
Conclusion
This blog discusses how to find gcd of two numbers with a concept of backtracking. Finding gcd of two numbers will enhance your logic and with stronger logics you can easily crack your dream job. Many complicated problems require basic fundamentals like finding gcd of two numbers. If you are a beginner in a coding career, then understanding problems like finding gcd of two numbers as for starting the basic logics are the must to practice stuff. Having knowledge about backtracking will make your competitive programming more stronger. To practice more problems on backtracking you can check out MYCODE | Competitive Programming.
FAQ for finding GCD of two numbers
1. What is the GCD of 24 and 42?
So, the highest/greatest common factor of 24 and 42 is 6 .
2. What is GCD or HCF?
GCD (Greatest Common Divisor) or HCF (Highest Common Factor) of two numbers is the largest number that divides both of them. For example, GCD of 20 and 28 is 4 and GCD of 98 and 56 is 14
3. Which companies asked questions like GCD of two numbers in their interview process?
Wipro, TCS, Accenture, Cognizant, Capegimini and Infosys generally asked to find GCD of two numbers in their interview.
You can refer the below links for practicing similar questions:
1. Armstrong number in Java
2. Convert binary to decimcal in C
3. Pattern program in C++