I am implementing Happy Number program. Happy number is a number which eventually reaches 1 when replaced by the sum of the square of each digit, and a number is not happy number if there are 2 duplicate numbers in the sequence.

For instance:

7 --> 0^2   7^2 = 49 --> 4^2   9^2 = 97 --> 130 --> 10 --> 1 --> happy number
18 --> 65 --> 61 --> |37| --> 58 --> 89 --> 145 --> 42 --> 20 --> 4 --> 16 --> |37| --> not happy number

My idea is to store the result of each operation to an array, then traverse that array to check if the array has duplicate number. But I think it is inefficient to do that.

So I want to ask how to find an element fast in a random order array, and is there a more efficient solution for the program?

Any help would be appreciated.

CodePudding user response：

Note that for a number of 4 digits, the number that comes next is 9² 9² 9² 9² = 324, a 3-digit number.

So for any number of ≥4 digits (without leading zeros), the next number in the sequence clearly decreases, so you won't have duplicates until you reach an number that has 3 digits, at max.

Then, you could create an array called wasAlreadyCalculated[999] that informs if that number has already been calculated in the sequence. So, when you go a step up, you check if that number was already checked. If yes, you don't have a happy number. otherwise, you mark that number as checked and keep going on until you find 1 or find a duplicate.

Not exactly the cleanest way, but it's efficient and it works.