Concepts Used:
Mathematics
Difficulty Level:
Hard
Problem Statement (Simplified):
For given two large numbers
M
andN
, find theirgcd(M,N)
.
GCD(M,N)
is the larget number possible which divides both.
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 :
1) For provided numbers, we know
N
is of size less than or equal to100
, so we would need to store this number in a string.2) We know we get the remainder less than
N
always if we divide any number byN
.3) To get the remainder by dividing a number stored
String
byNumber
, we calculate the remainder digit by digit. We update the remainder at every digit until all string is iterated.4) In each iteration, we take the digit and make it greater than our current remainder by multiplying it by 10 and adding it to digit, no we take
mod
of digit byN
and store as our current remainder. After the whole string is iterated, we get our remainder.5) After we divide
M
byN
and extract it's remainder, now both of them are of in Long Integer range, and we can carry with ourLong Division Method
for gettinggcd(M
,N)where
M is our new smaller number.6)
Long Division Method
: We repeatedly store remainder i.e (Larger number
%Smaller number
) and updateLarger number
bySmaller number
untilsmaller number
completely divides thelarger number
. LastSmaller Number
after all steps, is ourgcd
.
Example:
We'll be given with two nmubers out of which one is
string
and one islong
number. Hence we find remainder ofstring
number andlong
number.We can dry run above mentioned techinque,let's say given numbers are
143254
and 3, so first we convert143254
tolong
number which will be143254
%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 long division method, to find out gcd of both number that is
gcd(n,mod)
.Let's take 25 and 135 for example, we find
gcd
of both usingLong Division Method
.
As soon as our
remainder
becomes0
,dividend
is ourgcd(a,b)
.
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--; } } }
[forminator_quiz id="1157"]
This article tried to discuss Backtracking. Hope this blog helps you understand and solve the problem. To practice more problems on backtracking you can check out MYCODE | Competitive Programming.