{"id":2879,"date":"2023-08-18T17:55:17","date_gmt":"2023-08-18T12:25:17","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2879"},"modified":"2023-08-18T17:56:35","modified_gmt":"2023-08-18T12:26:35","slug":"happy-number","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/happy-number\/","title":{"rendered":"Happy Number"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\" style=\"max-width:400px\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">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=\"#approach-1-cycle-detection-using-hashset\">Approach 1: Cycle Detection using HashSet<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c--code\">C++ <meta charset=\"utf-8\">Code<\/a><\/li><li><a href=\"#java--code\">Java <meta charset=\"utf-8\">Code<\/a><\/li><li><a href=\"#python--code\">Python <meta charset=\"utf-8\">Code<\/a><\/li><\/ul><li><a href=\"#approach-2-floyd\u2019s-cycle-detection-algorithm\">Approach 2: Floyd\u2019s Cycle Detection Algorithm<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c--implementation\">C++ <meta charset=\"utf-8\">Implementation<\/a><\/li><li><a href=\"#java--implementation\">Java <meta charset=\"utf-8\">Implementation<\/a><\/li><li><a href=\"#python--implementation\">Python <meta charset=\"utf-8\">Implementation<\/a><\/li><\/ul><li><a href=\"#practice-question\">Practice Question<\/a><\/li><li><a href=\"#faq\">FAQ<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#q1-how-do-you-handle-the-case-if-the-integer-goes-on-increasing-till-infinity\">Q.1: How do you handle the case, if the integer goes on increasing till infinity?<\/a><\/li><li><a href=\"#q2-what-is-floyd\u2019s-cycle-detection-algorithm\">Q.2: What is Floyd\u2019s cycle detection algorithm?<\/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 an integer <strong>N.<\/strong> The task is to determine if <strong>N<\/strong> is a Happy Number.<\/p>\n\n\n\n<p>A&nbsp; Happy number is a number defined by the following process:<\/p>\n\n\n\n<ul><li>Start with any positive integer, and replace the number with the sum of the squares of its digits.<\/li><li>Repeat the process until the number equals 1, or it loops endlessly in a cycle which does not include 1.<\/li><li>Those numbers for which this process ends in 1 are happy numbers.<\/li><\/ul>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<ul><li><strong>Input: <\/strong>N = 97<\/li><li><strong>Output: <\/strong>True<\/li><\/ul>\n\n\n\n<p><strong>Explanation:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"450\"  height=\"500\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Output Explanation\"  class=\"wp-image-3164 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 450px) 100vw, 450px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/output-expanantion.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/output-expanantion.png 450w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/output-expanantion-270x300.png 270w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/output-expanantion-380x422.png 380w\" ><\/figure>\n\n\n\n<p><strong>Input: <\/strong>&nbsp;N = 2<br><strong>Output:<\/strong> False<\/p>\n\n\n\n<h2 id=\"approach-1-cycle-detection-using-hashset\">Approach 1: Cycle Detection using HashSet<\/h2>\n\n\n\n<p>Let us understand this approach with an example.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"970\"  height=\"192\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Cycle Detection using HashSet\"  class=\"wp-image-3165 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 970px) 100vw, 970px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Cycle-Detection-using-HashSet.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Cycle-Detection-using-HashSet.png 970w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Cycle-Detection-using-HashSet-300x59.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Cycle-Detection-using-HashSet-768x152.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Cycle-Detection-using-HashSet-380x75.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Cycle-Detection-using-HashSet-550x109.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Cycle-Detection-using-HashSet-800x158.png 800w\" ><\/figure>\n\n\n\n<p>Let us dry run the following:<br><\/p>\n\n\n\n<ul><li>N = 7<\/li><li>Squaring, N = 49. Now, N = 4^2 + 9 ^ 2 = 97.&nbsp;<\/li><li>N = 9^2 + 7^2 = 130<\/li><li>N = 1^2 + 3^2 + 0^2 = 10<\/li><li>N = 1^0 + 0^2 = 1<\/li><\/ul>\n\n\n\n<p>So, N becomes 1, hence, <strong>7<\/strong> is a happy number.<\/p>\n\n\n\n<p>Let us take another example, where the number remains in a loop.<\/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=\"number remains in a loop\"  class=\"wp-image-3166 pk-lazyload\"  width=\"700\"  height=\"360\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 700px) 100vw, 700px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/number-remains-in-a-loop.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/number-remains-in-a-loop.png 970w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/number-remains-in-a-loop-300x155.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/number-remains-in-a-loop-768x396.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/number-remains-in-a-loop-380x196.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/number-remains-in-a-loop-550x284.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/number-remains-in-a-loop-800x412.png 800w\" ><\/figure>\n\n\n\n<p>In the above example, it can be clearly observed that, after a few steps, the loops remains in a loop and can never reach 1, hence 116 is not a happy number.<\/p>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>Initialise a hashset to determine whether an integer has occurred previously or not.<\/li><li>Initialise an integer with <strong>N<\/strong> and the next integer generated would be the sum of squares of digits of the current integer.<\/li><li>Repeat the above process, until <strong>N<\/strong> reaches 1 or a number which has previously occurred again appears, i.e. enters into a cycle.<\/li><li>Return <strong>True<\/strong> if N reaches 1, else return <strong>False.<\/strong><\/li><\/ul>\n\n\n\n<h3 id=\"c--code\"><span id=\"c-code\">C++ <meta charset=\"utf-8\">Code<\/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=\"\">int getNext(int n) {\n        int totalSum = 0;\n        while (n > 0) {\n            int d = n % 10;\n            n = n \/ 10;\n            totalSum += d * d;\n        }\n        return totalSum;\n    }\n \n    bool isHappy(int n) {\n        set&lt;int> seen;\n        while (n != 1 &amp;&amp; seen.find(n) == seen.end()) {\n            seen.insert(n);\n            n = getNext(n);\n        }\n        return n == 1;\n    }<\/pre>\n\n\n\n<h3 id=\"java--code\"><span id=\"java-code\">Java <meta charset=\"utf-8\">Code<\/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=\"\">private int getNext(int n) {\n        int totalSum = 0;\n        while (n > 0) {\n            int d = n % 10;\n            n = n \/ 10;\n            totalSum += d * d;\n        }\n        return totalSum;\n    }\n \n    public boolean isHappy(int n) {\n        Set&lt;Integer> seen = new HashSet&lt;>();\n        while (n != 1 &amp;&amp; !seen.contains(n)) {\n            seen.add(n);\n            n = getNext(n);\n        }\n        return n == 1;\n    }<\/pre>\n\n\n\n<h3 id=\"python--code\"><span id=\"python-code\">Python <meta charset=\"utf-8\">Code<\/span><\/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 get_next(n):\n        total_sum = 0\n        while n > 0:\n            n, digit = divmod(n, 10)\n            total_sum += digit ** 2\n        return total_sum\n \n    seen = set()\n    while n != 1 and n not in seen:\n        seen.add(n)\n        n = get_next(n)\n \n    return n == 1<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(logN)<br><strong>Space Complexity:<\/strong> O(N), since HashSet is used.<\/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=\"approach-2-floyd\u2019s-cycle-detection-algorithm\"><span id=\"approach-2-floyds-cycle-detection-algorithm\">Approach 2: Floyd\u2019s Cycle Detection Algorithm<\/span><\/h2>\n\n\n\n<p>If an integer is not a Happy number, after certain steps it gets into the cycle. Now, this cycle can be thought of as a linked list and then our task would be to simply detect if a cycle exists in a linked list.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"970\"  height=\"500\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Floyds Cycle Detection\"  class=\"wp-image-3167 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 970px) 100vw, 970px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Floyds-Cycle-Detection.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Floyds-Cycle-Detection.png 970w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Floyds-Cycle-Detection-300x155.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Floyds-Cycle-Detection-768x396.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Floyds-Cycle-Detection-380x196.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Floyds-Cycle-Detection-550x284.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Floyds-Cycle-Detection-800x412.png 800w\" ><\/figure>\n\n\n\n<p><strong>Floyd\u2019s Cycle Detection Algorithm <\/strong>is based on two-pointers- <strong>fast <\/strong>and <strong>slow <\/strong>pointers. The slow pointer moves ahead by one step at a time, whereas the <strong>fast<\/strong> pointer moves ahead by two steps at a time. In case, there is a cycle, both the <strong>fast <\/strong>and <strong>slow <\/strong>pointer eventually meet after at a certain point.<\/p>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>Initialise slow pointer with <strong>N<\/strong> and fast pointer with the sum of squares of digits of <strong>N<\/strong>.<\/li><li>While <strong>fast pointer<\/strong> doesn\u2019t become equal to <strong>1<\/strong> and <strong>slow <\/strong>and <strong>fast <\/strong>pointer doesn\u2019t meet,<ul><li>Replace <strong>slow <\/strong>with the sum of squares of digits of <strong>slow.<\/strong><\/li><li>Replace <strong>fast <\/strong>with the sum of squares of digits of <strong>fast.<\/strong><\/li><\/ul><\/li><li>Return <strong>True<\/strong> if <strong>fast <\/strong>becomes 1, else return <strong>False.<\/strong><\/li><\/ul>\n\n\n\n<h3 id=\"c--implementation\"><span id=\"c-implementation\">C++ <meta charset=\"utf-8\">Implementation<\/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=\"\">int getNext(int n) {\n        int totalSum = 0;\n        while (n > 0) {\n            int d = n % 10;\n            n = n \/ 10;\n            totalSum += d * d;\n        }\n        return totalSum;\n    }\n \n    bool isHappy(int n) {\n        int slowRunner = n;\n        int fastRunner = getNext(n);\n        while (fastRunner != 1 &amp;&amp; slowRunner != fastRunner) {\n            slowRunner = getNext(slowRunner);\n            fastRunner = getNext(getNext(fastRunner));\n        }\n        return fastRunner == 1;\n    }\n}<\/pre>\n\n\n\n<h3 id=\"java--implementation\"><span id=\"java-implementation\">Java <meta charset=\"utf-8\">Implementation<\/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=\"\">public int getNext(int n) {\n        int totalSum = 0;\n        while (n > 0) {\n            int d = n % 10;\n            n = n \/ 10;\n            totalSum += d * d;\n        }\n        return totalSum;\n    }\n \n    public boolean isHappy(int n) {\n        int slowRunner = n;\n        int fastRunner = getNext(n);\n        while (fastRunner != 1 &amp;&amp; slowRunner != fastRunner) {\n            slowRunner = getNext(slowRunner);\n            fastRunner = getNext(getNext(fastRunner));\n        }\n        return fastRunner == 1;\n    }\n}<\/pre>\n\n\n\n<h3 id=\"python--implementation\"><span id=\"python-implementation\">Python <meta charset=\"utf-8\">Implementation<\/span><\/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 get_next(number):\n        total_sum = 0\n        while number > 0:\n            number, digit = divmod(number, 10)\n            total_sum += digit ** 2\n        return total_sum\n \n    slow_runner = n\n    fast_runner = get_next(n)\n    while fast_runner != 1 and slow_runner != fast_runner:\n        slow_runner = get_next(slow_runner)\n        fast_runner = get_next(get_next(fast_runner))\n    return fast_runner == 1<\/pre>\n\n\n\n<ul><li><strong>Time Complexity:<\/strong> O(logN)<\/li><li><strong>Space Complexity:<\/strong> O(1)<\/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=\"practice-question\">Practice Question<\/h2>\n\n\n\n<ul><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/n-digit-numbers-with-digit-sum-s-\/\" target=\"_blank\">N digit numbers with digit sum S<\/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=\"faq\">FAQ<\/h2>\n\n\n\n<h3 id=\"q1-how-do-you-handle-the-case-if-the-integer-goes-on-increasing-till-infinity\"><span id=\"q-1-how-do-you-handle-the-case-if-the-integer-goes-on-increasing-till-infinity\">Q.1: How do you handle the case, if the integer goes on increasing till infinity?<\/span><\/h3>\n\n\n\n<p><strong>Ans: <\/strong>You do not need to explicitly handle this case, since any number until a 32-bit integer would remain in a cycle of 1053(The sum of squares of digits of 9999999999999 is 1053).<\/p>\n\n\n\n<h3 id=\"q2-what-is-floyd\u2019s-cycle-detection-algorithm\"><span id=\"q-2-what-is-floyds-cycle-detection-algorithm\">Q.2: What is Floyd\u2019s cycle detection algorithm?<\/span><\/h3>\n\n\n\n<p><strong>Ans:<\/strong> Floyd\u2019s Cycle Detection Algorithm is based on two-pointers- fast and slow pointers. The slow pointer moves ahead by one step at a time, whereas the fast pointer moves ahead by two steps at a time. In case, there is a cycle, both the fast and slow pointers eventually meet at a certain point.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given an integer N. The task is to determine if N is a Happy Number. A&nbsp;&hellip;\n","protected":false},"author":4,"featured_media":3168,"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":[473],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2879"}],"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\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=2879"}],"version-history":[{"count":7,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2879\/revisions"}],"predecessor-version":[{"id":22980,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2879\/revisions\/22980"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3168"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2879"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2879"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2879"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}