Leetcode algorithm exercise for finding happy number

Question

Background:

This problem comes from leetcode.com

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

1^2 + 9^2 = 82

8^2 + 2^2 = 68

6^2 + 8^2 = 100

1^2 + 0^2 + 0^2 = 1

Question:

I thought of doing a recursion for this particular problem to keep repeating the squaring of the integers until we arrive at 1. I am new with recursion (just read Absolute C++ Ch 13 --- Recursion yesterday).I thought I would give this problem a shot but I am having some trouble.

When I call my function I created I should get a return of 19 since 19 is a "Happy Number", but instead my function just returns 0, and I am not sure why. I just need some help with my approach I have taken and suggestions to changes in my code.

Here is my code:

#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;


int Happy(int n) {
    vector<int> nums;
    int length = to_string(n).length();
        for(int i = 0; i < length; i++) {
            int digit = n % 10;
            n /= 10;
            nums.push_back(digit);
        }
        reverse(nums.begin(), nums.end());
        int sum = 0;
        for(int i = 0; i < length; i++) {
             sum += pow(nums[i],2);
        }
    if (sum == 1) {
        return n;
    }
    else {
        return Happy(sum);
    }
}



int main() {
    int n = 19;
    int result = Happy(n);
    cout << result << endl;

    return 0;
}

Again, I am not sure why I get 0 as the result, when it should return 19.

You are missing something in the `else` branch (which causes your code to invoke *undefined behavior*) — UnholySheep, Jan 31 '18 at 21:34
@UnholySheep Do you know what it is I am missing, am I calling the recursion incorrectly? — Wolfy, Jan 31 '18 at 21:35
Your `else` branch does not use the return value of the function it calls. Also it doesn't return anything itself (though it should be, as the function is declared to return an `int`) — UnholySheep, Jan 31 '18 at 21:35
@Wolfy `pow(nums[i],2)` -- [Don't do this](https://stackoverflow.com/questions/25678481/why-does-pown-2-return-24-when-n-5-with-my-compiler-and-os) Not only isn't it guaranteed to give you the correct results, it slows the code down by invoking floating point routines. — PaulMcKenzie, Jan 31 '18 at 21:50

zenwraight · Accepted Answer · 2018-01-31T23:21:03.950

3

You forgot to place a return in your code, Also you n becomes 0, and you are returning n when you find sum == 1. It should return the original_num.

To Store the original number reference pass it along with your call to happy method.

#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;


int Happy(int n, int original_num) {
    vector<int> nums;
    int length = to_string(n).length();
        for(int i = 0; i < length; i++) {
            int digit = n % 10;
            n /= 10;
            nums.push_back(digit);
        }
        //reverse(nums.begin(), nums.end());
        int sum = 0;
        for(int i = 0; i < length; i++) {
             sum += nums[i]*nums[i];
        }
    if (sum == 1) {
        return original_num;
    }
    else {
        return Happy(sum, original_num);
    }
}



int main() {
    int n = 19;
    int result = Happy(n, n);
    cout << result << endl;

    return 0;
}

Hope this helps!

edited Jan 31 '18 at 23:21

answered Jan 31 '18 at 21:35

zenwraight

2,002
1
10
14

@Wolfy try this code now, you will understand your mistake – zenwraight Jan 31 '18 at 21:39
Just curious I know I initially got downvotes any reason why? – Wolfy Jan 31 '18 at 21:41
glad it helped, there are no specific reasons for downvotes, generally these types are questions shouldn't be asked here. You can mark this as answer if it helped you – zenwraight Jan 31 '18 at 21:42
@zenwraight -- Read my comment in the main post about using `pow`. By using `pow` you will turn an integer solution into a floating point one. – PaulMcKenzie Jan 31 '18 at 21:52
Also, when the number is not "Happy" it will recurse until it runs out of stack and crashes, so you would want to have some way to prevent this and also indicate that you either don't know or have given up. – Ian4264 Jan 31 '18 at 22:42
Good point @Ian4264, I assumed that this condition would, also I just wanted to point out what mistake the author of the code is making. I will place a condition for it – zenwraight Jan 31 '18 at 23:20

Leetcode algorithm exercise for finding happy number

1 Answers1