Given two numbers n and m. Find the biggest integer a(gcd), such that all integers n, n + 1, n + 2, …, m are divisible by a.
Examples:
Input : n = 1, m = 2 Output: 1 Explanation: Here, series become 1, 2. So, the greatest no which divides both of them is 1. Input : n = 475, m = 475 Output : 475 Explanation: Here, series has only one term 475. So, greatest no which divides 475 is 475.
Here, We have to examine only two cases:
- if a = b : the segment consists of a single number, hence the answer is a.
- if a < b : we have gcd(n, n + 1, n?+ 2, …, m) = gcd(gcd(n, n + 1), n + 2, …, m) = gcd(1, n + 2, …, n) = 1.
C++
// GCD of given range#include <bits/stdc++.h>using namespace std; int rangeGCD(int n, int m){ return (n == m)? n : 1;} int main(){ int n = 475; int m = 475; cout << rangeGCD(n, m); return 0;} |
Java
// GCD of given range import java.io.*; class GFG { static int rangeGCD(int n, int m) { return (n == m) ? n : 1; } public static void main(String[] args) { int n = 475; int m = 475; System.out.println(rangeGCD(n, m)); }} // This code is contributed by Ajit. |
Python3
# GCD of given range def rangeGCD(n, m): return n if(n == m) else 1 # Driver coden, m = 475, 475print(rangeGCD(n, m)) # This code is contributed by Anant Agarwal. |
C#
// GCD of given rangeusing System; class GFG { static int rangeGCD(int n, int m) { return (n == m) ? n : 1; } public static void Main() { int n = 475; int m = 475; Console.WriteLine(rangeGCD(n, m)); }} // This code is contributed by Anant Agarwal. |
PHP
<?php// PHP program for // GCD of given range // function returns the GCDfunction rangeGCD($n, $m){ return ($n == $m)? $n : 1;} // Driver Code $n = 475; $m = 475; echo rangeGCD($n, $m); // This code is contributed by anuj_67.?> |
Javascript
<script>// GCD of given range function rangeGCD( n, m) { return (n == m) ? n : 1; } var n = 475; var m = 475; document.write(rangeGCD(n, m));</script> |
Output:
475
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
