{"id":33764,"date":"2024-11-01T09:20:06","date_gmt":"2024-11-01T09:20:06","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33764"},"modified":"2024-11-01T11:46:47","modified_gmt":"2024-11-01T11:46:47","slug":"python-coding-test-course-finding-the-least-common-multiple","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33764\/","title":{"rendered":"Python Coding Test Course, Finding the Least Common Multiple"},"content":{"rendered":"<p>Hello! In this post, we will take a detailed look at how to calculate the &#8216;Least Common Multiple (LCM)&#8217; through solving algorithmic problems. The least common multiple is the smallest number among the common multiples of two or more integers. It is important to thoroughly understand and practice this problem as it frequently appears in programming interviews and coding tests.<\/p>\n<h2>Problem Definition<\/h2>\n<p>Write a function to find the least common multiple of the two given integers A and B.<\/p>\n<h3>Input<\/h3>\n<ul>\n<li>Two integers A and B (1 \u2264 A, B \u2264 100,000)<\/li>\n<\/ul>\n<h3>Output<\/h3>\n<ul>\n<li>The least common multiple (LCM) of A and B<\/li>\n<\/ul>\n<h3>Example<\/h3>\n<pre>\nInput: \n4 5\n\nOutput: \n20\n<\/pre>\n<h2>Problem Approach<\/h2>\n<p>To calculate the least common multiple, it is efficient to utilize the Greatest Common Divisor (GCD). The least common multiple can be obtained using the following formula:<\/p>\n<p>LCM(A, B) = (A \u00d7 B) \/ GCD(A, B)<\/p>\n<p>The origin of this formula comes from the definition of multiples of two numbers and the properties of the greatest common divisor. Dividing the product of the two numbers by the greatest common divisor leaves only the multiples that those numbers do not share.<\/p>\n<h2>Calculating GCD in Python<\/h2>\n<p>In Python, you can easily find the greatest common divisor by using the built-in math module.<\/p>\n<h2>Writing Code to Solve the Problem<\/h2>\n<p>Now, let&#8217;s implement a function to calculate the least common multiple step by step.<\/p>\n<pre>\nimport math\n\ndef lcm(a: int, b: int) -> int:\n    return (a * b) \/\/ math.gcd(a, b)\n\n# Test the function\na, b = map(int, input(\"Enter two integers: \").split())\nprint(f\"The least common multiple of {a} and {b} is {lcm(a, b)}.\")\n<\/pre>\n<h3>Code Explanation<\/h3>\n<ul>\n<li>First, we import the <code>math<\/code> module to use the <code>gcd<\/code> function.<\/li>\n<li>We define the <code>lcm<\/code> function, which takes two integers as parameters and returns the least common multiple.<\/li>\n<li>Finally, we take user input to test the function.<\/li>\n<\/ul>\n<h2>Test Cases<\/h2>\n<p>Now, let&#8217;s verify if the function works correctly with various input values.<\/p>\n<pre>\n# Test Cases\nprint(lcm(4, 5))  # Output: 20\nprint(lcm(12, 15))  # Output: 60\nprint(lcm(7, 3))  # Output: 21\nprint(lcm(100, 10))  # Output: 100\nprint(lcm(27, 36))  # Output: 108\n<\/pre>\n<h2>Complexity Analysis<\/h2>\n<p>Now let&#8217;s analyze the time and space complexity of the code.<\/p>\n<ul>\n<li>Time Complexity: By using the Euclidean algorithm to calculate the GCD, it has a time complexity of O(log(min(A, B))). Thus, the overall complexity of finding the LCM is also O(log(min(A, B))).<\/li>\n<li>Space Complexity: Constant space O(1) as it does not use any additional memory.<\/li>\n<\/ul>\n<h2>Conclusion<\/h2>\n<p>In this post, we implemented an algorithm to find the least common multiple of two numbers using Python. This problem has been a great opportunity to review the concepts of divisors and multiples. It is a common type that appears in coding tests, so I encourage you to practice thoroughly.<\/p>\n<p>In the next post, I will come back with a wider variety of problems. Thank you for your interest!<\/p>\n<h2>References<\/h2>\n<ul>\n<li><a href=\"https:\/\/docs.python.org\/3\/library\/math.html#math.gcd\">Python Math Documentation<\/a><\/li>\n<li><a href=\"https:\/\/en.wikipedia.org\/wiki\/Least_common_multiple\">Wikipedia &#8211; Least Common Multiple<\/a><\/li>\n<li><a href=\"https:\/\/en.wikipedia.org\/wiki\/Greatest_common_divisor\">Wikipedia &#8211; Greatest Common Divisor<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Hello! In this post, we will take a detailed look at how to calculate the &#8216;Least Common Multiple (LCM)&#8217; through solving algorithmic problems. The least common multiple is the smallest number among the common multiples of two or more integers. It is important to thoroughly understand and practice this problem as it frequently appears in &hellip; <a href=\"https:\/\/atmokpo.com\/w\/33764\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;Python Coding Test Course, Finding the Least Common Multiple&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[145],"tags":[],"class_list":["post-33764","post","type-post","status-publish","format-standard","hentry","category-python-coding-test"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Python Coding Test Course, Finding the Least Common Multiple - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/atmokpo.com\/w\/33764\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Python Coding Test Course, Finding the Least Common Multiple - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Hello! In this post, we will take a detailed look at how to calculate the &#8216;Least Common Multiple (LCM)&#8217; through solving algorithmic problems. The least common multiple is the smallest number among the common multiples of two or more integers. It is important to thoroughly understand and practice this problem as it frequently appears in &hellip; \ub354 \ubcf4\uae30 &quot;Python Coding Test Course, Finding the Least Common Multiple&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/33764\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:20:06+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:46:47+00:00\" \/>\n<meta name=\"author\" content=\"root\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:site\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:label1\" content=\"\uae00\uc4f4\uc774\" \/>\n\t<meta name=\"twitter:data1\" content=\"root\" \/>\n\t<meta name=\"twitter:label2\" content=\"\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04\" \/>\n\t<meta name=\"twitter:data2\" content=\"2\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/33764\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33764\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"Python Coding Test Course, Finding the Least Common Multiple\",\"datePublished\":\"2024-11-01T09:20:06+00:00\",\"dateModified\":\"2024-11-01T11:46:47+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33764\/\"},\"wordCount\":428,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Python Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/33764\/\",\"url\":\"https:\/\/atmokpo.com\/w\/33764\/\",\"name\":\"Python Coding Test Course, Finding the Least Common Multiple - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:20:06+00:00\",\"dateModified\":\"2024-11-01T11:46:47+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33764\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/33764\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/33764\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Python Coding Test Course, Finding the Least Common Multiple\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/atmokpo.com\/w\/#website\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/atmokpo.com\/w\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"ko-KR\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"contentUrl\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"width\":400,\"height\":400,\"caption\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\"},\"image\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/x.com\/bebubo4\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\",\"name\":\"root\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"caption\":\"root\"},\"sameAs\":[\"http:\/\/atmokpo.com\/w\"],\"url\":\"https:\/\/atmokpo.com\/w\/author\/root\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Python Coding Test Course, Finding the Least Common Multiple - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/atmokpo.com\/w\/33764\/","og_locale":"ko_KR","og_type":"article","og_title":"Python Coding Test Course, Finding the Least Common Multiple - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Hello! In this post, we will take a detailed look at how to calculate the &#8216;Least Common Multiple (LCM)&#8217; through solving algorithmic problems. The least common multiple is the smallest number among the common multiples of two or more integers. It is important to thoroughly understand and practice this problem as it frequently appears in &hellip; \ub354 \ubcf4\uae30 \"Python Coding Test Course, Finding the Least Common Multiple\"","og_url":"https:\/\/atmokpo.com\/w\/33764\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:20:06+00:00","article_modified_time":"2024-11-01T11:46:47+00:00","author":"root","twitter_card":"summary_large_image","twitter_creator":"@bebubo4","twitter_site":"@bebubo4","twitter_misc":{"\uae00\uc4f4\uc774":"root","\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04":"2\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/33764\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/33764\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"Python Coding Test Course, Finding the Least Common Multiple","datePublished":"2024-11-01T09:20:06+00:00","dateModified":"2024-11-01T11:46:47+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/33764\/"},"wordCount":428,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Python Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/33764\/","url":"https:\/\/atmokpo.com\/w\/33764\/","name":"Python Coding Test Course, Finding the Least Common Multiple - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:20:06+00:00","dateModified":"2024-11-01T11:46:47+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/33764\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/33764\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/33764\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"Python Coding Test Course, Finding the Least Common Multiple"}]},{"@type":"WebSite","@id":"https:\/\/atmokpo.com\/w\/#website","url":"https:\/\/atmokpo.com\/w\/","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","description":"","publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/atmokpo.com\/w\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"ko-KR"},{"@type":"Organization","@id":"https:\/\/atmokpo.com\/w\/#organization","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","url":"https:\/\/atmokpo.com\/w\/","logo":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/","url":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","contentUrl":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","width":400,"height":400,"caption":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8"},"image":{"@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/x.com\/bebubo4"]},{"@type":"Person","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7","name":"root","image":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","caption":"root"},"sameAs":["http:\/\/atmokpo.com\/w"],"url":"https:\/\/atmokpo.com\/w\/author\/root\/"}]}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33764","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/comments?post=33764"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33764\/revisions"}],"predecessor-version":[{"id":33765,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33764\/revisions\/33765"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=33764"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=33764"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=33764"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}