CODEWITHSUNDEEP
c++mathnumberscombinationsnumber-theory
rishi
rishi

Reputation: 65

Fast way to find a unhappy number

I'm trying to solve a question. Given a range of integers user has to find the number of unhappy present in the given range.

Unhappy number- a number n such that iterating this sum-of-squared-digits map starting with n never reaches the number 1.

I've tried using the brute force approach by calculating the sum of the squares of digits and if at any instant it is equal to any of these (4, 16, 37, 58, 89, 145, 42, 20) then it is a unhappy number.

This approach is giving TLE is there any better method??

Range is between 1 to 10^18.

Upvotes: 1

Views: 722

Answers (2)

orlp
orlp

Reputation: 117771

Your range is between 1 and 1018. This means your numbers have a maximum of 18 digits.

Consider that the maximum square of a digit is 92 = 81, after doing the squared-digit-sum once the maximum number is 18 * 81 = 1458.

So one squared-digit-sum plus a lookup table of ~1500 elements should suffice.

Or two squared-digit-sums plus a lookup table of ~330 elements:

static const bool unhappy[330] {
    1,0,1,1,1,1,1,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,0,1,1,0,0,1,1,1,1,1,
    1,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,
    1,1,1,0,1,1,0,1,1,1,0,1,1,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1,1,1,
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,
    0,1,0,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,
    1,1,0,1,1,1,1,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,0,0,1,
    1,1,1,1,1,1,0,1,1,0,1,1,1,1,1,0,0,1,1,1,1,1,0,1,1,0
}

inline bool is_unhappy(uint64_t n) {
    while (n >= 330) {
        int r = 0;
        while (n > 0) {
            int d = n % 10;
            r += d*d;
            n /= 10;
        }
        n = r;
    }

    return unhappy[n];
}

Upvotes: 4

gsamaras
gsamaras

Reputation: 73394

#include <map>
#include <set>

bool happy(int number) {
    static std::map<int, bool> cache;

    std::set<int> cycle;
    while (number != 1 && !cycle.count(number)) {
        if (cache.count(number)) {
            number = cache[number] ? 1 : 0;
            break;
        }
        cycle.insert(number);
        int newnumber = 0;
        while (number > 0) {
            int digit = number % 10;
            newnumber += digit * digit;
            number /= 10;
        }
        number = newnumber;
    }
    bool happiness = number == 1;
    for (std::set<int>::const_iterator it = cycle.begin();
    it != cycle.end(); it++)
    cache[*it] = happiness;
    return happiness;
}

#include <iostream>

int main() {
    for (int i = 1; i < 10; i++)
      if (!happy(i))
        std::cout << i << std::endl;
    return 0;
}

Output:

2
3
4
5
6
8
9

Logic and most of the code taken from here: https://tfetimes.com/c-happy-numbers/

Upvotes: 0

Related Questions