{"id":2160,"date":"2023-03-27T12:25:03","date_gmt":"2023-03-27T06:55:03","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2160"},"modified":"2023-03-27T12:25:40","modified_gmt":"2023-03-27T06:55:40","slug":"gcd-of-two-numbers","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/gcd-of-two-numbers\/","title":{"rendered":"GCD of Two Numbers (C, Python, Java) With Examples"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"text_open\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#simple-approach\">Simple Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#python-implementation\">Python Implementation<\/a><\/li><li><a href=\"#java-implementation\">Java Implementation<\/a><\/li><\/ul><li><a href=\"#efficient-approach-euclid\u2019s-algorithm\">Efficient Approach: Euclid\u2019s Algorithm<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#cc-implementation-of-efficient-approach\">C\/C++ Implementation of Efficient Approach<\/a><\/li><li><a href=\"#-java-implementation-of-efficient-approach\"><meta charset=\"utf-8\">Java Implementation of Efficient Approach<\/a><\/li><li><a href=\"#python-implementation-of-efficient-approach\">Python Implementation of Efficient Approach<\/a><\/li><\/ul><li><a href=\"#practice-questions\">Practice Questions<\/a><\/li><li><a href=\"#frequently-asked-questions\">Frequently Asked Questions<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#q1-how-do-you-find-the-gcd-of-two-numbers\">Q1: How do you find the GCD of two numbers?<\/a><\/li><li><a href=\"#q2-can-we-find-the-gcd-of-negative-numbers\">Q2: Can we find the GCD of negative numbers?<\/a><\/li><li><a href=\"#q3-do-any-two-positive-integers-always-have-a-gcd\">Q3: Do any two positive integers always have a GCD?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given two non-negative integers a and b, we have to find their GCD (greatest common divisor),i.e. the largest number which is a divisor of both a and b. It&#8217;s commonly denoted by<br>gcd(a,b). Mathematically it is defined as<\/p>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img  loading=\"lazy\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"GCD\"  class=\"wp-image-2163 pk-lazyload\"  width=\"519\"  height=\"120\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 519px) 100vw, 519px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/image2.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/image2.png 402w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/image2-300x69.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/image2-380x88.png 380w\" ><\/figure>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<p><strong>Input:<\/strong> a=32, b=20<br><strong>Output:<\/strong> 4<br><strong>Explanation:<\/strong> 4 is the largest factor that divides both of the numbers.<\/p>\n\n\n\n<p><strong>Input:<\/strong> a=98, b=70<br><strong>Output:<\/strong> 14<br><strong>Explanation:<\/strong> 14 is the largest factor that divides both of the numbers.<\/p>\n\n\n\n<p><strong>Input:<\/strong> a=399, b=437<br><strong>Output:<\/strong> 19<br><strong>Explanation:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img  loading=\"lazy\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"HCF\"  class=\"wp-image-2164 pk-lazyload\"  width=\"563\"  height=\"313\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 563px) 100vw, 563px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/image3.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/image3.png 509w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/image3-300x167.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/image3-380x211.png 380w\" ><\/figure>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"simple-approach\">Simple Approach<\/h2>\n\n\n\n<p>We can traverse over all the numbers from min(A, B) to 1 and check if the current number divides both A and B or not. If it does, then it will be the GCD of A and B.<\/p>\n\n\n\n<h3 id=\"c-implementation\">C++ Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int GCD(int A, int B) {\n    int m = min(A, B), gcd;\n    for(int i = m; i > 0; --i)\n        if(A % i == 0 &amp;&amp; B % i == 0) {\n            gcd = i;\n            return gcd;\n        }\n}<\/pre>\n\n\n\n<h3 id=\"python-implementation\">Python Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def GCD_Loop( a, b):  \n    if a > b:  # define the if condition  \n        temp = b  \n    else:  \n        temp = a  \n    for i in range(1, temp + 1):  \n        if (( a % i == 0) and (b % i == 0 )):  \n            gcd = i  \n    return gcd <\/pre>\n\n\n\n<h3 id=\"java-implementation\">Java Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">class Main {\n  public static void main(String[] args) {\n\n    \/\/ find GCD between n1 and n2\n    int n1 = 81, n2 = 153;\n    \n    \/\/ initially set to gcd\n    int gcd = 1;\n\n    for (int i = 1; i &lt;= n1 &amp;&amp; i &lt;= n2; ++i) {\n\n      \/\/ check if i perfectly divides both n1 and n2\n      if (n1 % i == 0 &amp;&amp; n2 % i == 0)\n        gcd = i;\n    }\n\n    System.out.println(\"GCD of \" + n1 +\" and \" + n2 + \" is \" + gcd);\n  }\n}<\/pre>\n\n\n\n<p><strong>Time complexity:<\/strong> O(min(A, B))<br><strong>Space complexity:<\/strong> O(1)<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"efficient-approach-euclid\u2019s-algorithm\"><span id=\"efficient-approach-euclids-algorithm\">Efficient Approach: Euclid\u2019s Algorithm<\/span><\/h2>\n\n\n\n<p>The algorithm is based on the below facts.<\/p>\n\n\n\n<ul><li>When we have to reduce a larger number then what we can do in a simple manner is just subtract small numbers from larger numbers and from this we can notice GCD will not change. Hence we can keep subtracting the larger of two numbers, we end up with the GCD.<\/li><li>Now instead of doing subtraction, we can do one more thing i.e if we divide the smaller number, the algorithm stops when we find remainder 0.<\/li><\/ul>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"187\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Euclid\u2019s Algorithm\"  class=\"wp-image-2162 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/image1-1024x187.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/image1-1024x187.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/image1-300x55.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/image1-768x141.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/image1-1536x281.png 1536w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/image1-380x70.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/image1-550x101.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/image1-800x146.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/image1-1160x212.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/image1.png 1999w\" ><\/figure><\/div>\n\n\n\n<h3 id=\"cc-implementation-of-efficient-approach\"><span id=\"c-c-implementation-of-efficient-approach\">C\/C++ Implementation of Efficient Approach<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\/\/ Function to return\n\/\/ gcd of a and b\nint gcd(int a, int b) {\n  if (a == 0)\n    return b;\n  return gcd(b % a, a);\n}<\/pre>\n\n\n\n<h3 id=\"-java-implementation-of-efficient-approach\"><span id=\"java-implementation-of-efficient-approach\"><meta charset=\"utf-8\">Java Implementation of Efficient Approach<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">import java.util.*;\nimport java.lang.*;\n\nclass Interviewbit {\n  \/\/ extended Euclidean Algorithm\n  public static int gcd(int a, int b) {\n    if (a == 0)\n      return b;\n\n    return gcd(b % a, a);\n  }\n\n}<\/pre>\n\n\n\n<h3 id=\"python-implementation-of-efficient-approach\">Python Implementation of Efficient Approach<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def gcd(a, b):\n\tif a == 0 :\n\t\treturn b\n\t\n\treturn gcd(b%a, a)<\/pre>\n\n\n\n<p><strong>Time complexity:<\/strong> O(Log min(a, b)) where \u2018a\u2019 and \u2018b\u2019 are two numbers.<br><strong>Space complexity:<\/strong> O(1)<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"practice-questions\">Practice Questions<\/h2>\n\n\n\n<ul><li>Solve Problem: <a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/greatest-common-divisor\/\" target=\"_blank\">Greatest Common Divisor<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/largest-coprime-divisor\/\" target=\"_blank\">Largest Coprime Divisor<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/gcdcmpl\/\" target=\"_blank\">GCD CMPL<\/a><\/li><\/ul>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"frequently-asked-questions\">Frequently Asked Questions<\/h2>\n\n\n\n<h3 id=\"q1-how-do-you-find-the-gcd-of-two-numbers\">Q1: How do you find the GCD of two numbers?<\/h3>\n\n\n\n<p><strong>Ans:<\/strong> From the Euclidean algorithm as it has less time complexity (log(min(a,b))<\/p>\n\n\n\n<h3 id=\"q2-can-we-find-the-gcd-of-negative-numbers\">Q2: Can we find the GCD of negative numbers?<\/h3>\n\n\n\n<p><strong>Ans:<\/strong> Yes, GCD(6, -12) = GCD(-6, 12) = GCD(-6, -12) = GCD(6, 12) = 6.<\/p>\n\n\n\n<h3 id=\"q3-do-any-two-positive-integers-always-have-a-gcd\">Q3: Do any two positive integers always have a GCD?<\/h3>\n\n\n\n<p><strong>Ans<\/strong>: Yes, as it&#8217;s the largest factor dividing both numbers.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given two non-negative integers a and b, we have to find their GCD (greatest common divisor),i.e.&hellip;\n","protected":false},"author":5,"featured_media":10303,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[366,365],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2160"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=2160"}],"version-history":[{"count":5,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2160\/revisions"}],"predecessor-version":[{"id":17376,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2160\/revisions\/17376"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/10303"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2160"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2160"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2160"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}