CODEWITHSUNDEEP
c++optimization
Bijan
Bijan

Reputation: 8668

C++: Happy Number Endless Loop

I created a function to find the first X Happy Numbers.

A happy number is 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

My question is how do I know when it loops endlessly in a cycle? What I am currently doing is counting how many times it goes through the Sum Of Squares function and if it is > 10, it will just return 0. Here is my code..

C++

#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;

int k, rep = 0;

int SumOfSq(int num) {
    int total = 0;
    while(num) {
        int digit = num % 10;
        num /= 10;
        total += pow(digit,2);
    }
    return total;
}

bool Happy(int num) {
    int temp = 0;
    while(num != 1) {
        if(k == rep) exit(1);
        num = SumOfSq(num);
        if(temp++ > 10) {
            return 0; //Not happy
        }
    }
    rep++;
    return 1; //Happy
}

int main() {
    cout << "How many Happy Numbers to find? ";
    cin >> k;
    for(int j = 1;;j++) 
        if(Happy(j)) cout << j << " ";
}

Also please let me know if my code has any mistakes or thing to improve on. The current output should be correct.

Upvotes: 2

Views: 7500

Answers (6)

confused_
confused_

Reputation: 1691

Definition from WIKI: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number either equals 1 (where it will stay), or it loops endlessly in a cycle that does not include 1. Those numbers for which this process ends in 1 are happy numbers, while those that do not end in 1 are unhappy numbers (or sad numbers).

If any number is said to be happy then any number involving that sequence is also a happy number. Example: starting with 7 gives the sequence 7, 49, 97, 130, 10, 1, so 7 is a happy number.

Likewise, If any number is said to be unhappy then any number involving that sequence/cycle is also an unhappy number. Example: starting with 4 gives the sequence 4, 16, 37, 58, 89, 145, 42, 20, 4, which leads to a cycle, so 4 is an unhappy number.

Function to check if "n" is Happy number(return true) otherwise return false

class Solution {                                           
public:
   bool isHappy(int n) {                         // funtion to check 
   if (n <= 0) return false;                     // if negative cannot be a happy number

    int magic = 4;                                // it a unhappy number 
    while (1)
    {
    if (n == 1) return true;                  // if n becomes 1 then it is happy number 
    if (n == magic) return false;             // if n becomes equal to 4 then the cycle cannot become happy
    int t = 0;
    while (n)                                 
    {
        t += (n % 10) * (n % 10);             // adding square of digit square of digits
        n /= 10;
    }
    n = t;
    }
    }
};

Upvotes: 0

Suvam Roy
Suvam Roy

Reputation: 953

This is my C solution. Works fine for me.

#include<stdio.h>
int getnum(int num);
int breaksquaresum(int num);
int main()
{
    while(1){

    printf("Enter a number to check whether Happy Or Not \n");
    int k;
    scanf("%d",&k);
 int indicator= breaksquaresum(k);
    if(indicator == 1){
        printf("Number %d is Happy\n",k);
    }
    else{
        printf("Number %d is Not Happy!!\n",k);
    }
}
}

int breaksquaresum(int num)
{
    printf("%d num\n",num);
    int sum=0,rem;
    while(num!=0){
        rem=num%10;
        sum=sum+(rem*rem);
        printf("Sum %d\n",sum);
        num=num/10;

    }
    if(sum<10 && sum==1 || sum==7)
        return 1;

    if(sum<10 && sum!=1 && sum!=7 )
        return 0;

    breaksquaresum(sum);
}

Upvotes: 1

Gulzada Serzhan
Gulzada Serzhan

Reputation: 67

For the first 1000 happy numbers from the wiki on Happy numbers this is true:

if (temp++ > 5) { return 0; //Not happy }

i.e. you don't have to iterate more than 6 times.

Upvotes: 0

T3chN1nja
T3chN1nja

Reputation: 21

C code example for Happy Number sequence:

#include<stdio.h>
#include<math.h>
int happy(int t)
{
  long sum=0;
  int r;
  while(t>0)
  {
    r=t%10;
    t/=10;
    sum+=pow(r,2);
  }
  if(sum==4||sum==16||sum==37||sum==58||sum==89||sum==145||sum==42||sum==20)
    return 0;
  else if(sum==1)
    return sum;
  else
    return happy(sum);
}

int main()
{
    int n,i;
    printf("Enter the range: ");
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        if(happy(i)==1)
            printf("%d ",i);
    }
    return 0;
}

Upvotes: 2

dfeuer
dfeuer

Reputation: 48611

TheGoatMan7 gives a practical answer to the question, but I figured I should add an answer explaining, at least in part, how to get there. The number of digits in a positive integer n equals floor(log n/log 10)+1. The sum of the squares of the digits of that number, then, is bounded above by 81*floor(log n/log 10 + 1). You should be able to see that when n is sufficiently large, this will be less than n. That is, when n is large, the sum of the squares of the digits of n is less than n. Let's put a loose upper bound on that cutoff:

81*floor(log 1000/log 10+1) = 81*4 < 1000

You can see now that when n > 1000, the sum of the squares of the digits on n is less than n. Whatever number you start with, you'll eventually drop under 1000 and stay there, either stabilizing or looping through numbers under 1000. So you only need to worry about numbers under 1000, and loops that last at most 1000 steps. That's just a few million operations, easily done by brute force.

I just saw that the underlying question is about listing happy numbers, not checking whether numbers are happy. Doing this efficiently looks complicated, but I would probably start with this fact:

Theorem

n is a happy number if and only if every number m, the sum of the squares of whose digits are n, is a happy number. Now each non-zero natural is the sum of the squares of the digits of infinitely many other naturals, so it will take some care to put all these in the right order, but I conjecture that it will end up faster. Let's see how this starts.

1 is a happy number. Therefore so are 10, 100, 1000, 10000, ...

10=1+9=2*4+2*1=4+6*1=10*1 is a happy number. Therefore, so are 13, 31, 103, 301, 1003, 3001, ..., 1122,1212,1221,2112,2121,2211,10122,10212,10221,.... 1111112,1111121,1111211,1112111,1121111,1211111,2111111,10111112,10111121,..., 1111111111,10111111111,110111111111,...

These lists, of course, would need to be merged. This approach seems to trade the complicated arithmetic of the check-each-number approach for complicated bookkeeping. I don't know if there's a way to make that worth the trouble.

Upvotes: 3

TheGoatMan7
TheGoatMan7

Reputation: 610

From the wiki on Happy numbers:

If n is happy, then its sequence goes to 1. Otherwise, it ends in the cycle:

4, 16, 37, 58, 89, 145, 42, 20, 4, ...

So just look to see if you have landed on one of those numbers to see if you are in the unhappy cycle.

An alternative to keeping track of the numbers you've seen, which could be better if you plan on having many cases where you travel more than 8 numbers.

Upvotes: 6

Related Questions