C++: Happy Numbers

Bjarne-stroustrup
 

From Wikipedia, the free encyclopedia:

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. Those numbers for which this process ends in 1 are happy numbers, while those that do not end in 1 are unhappy numbers. Display an example of your output here.

Task: Find and print the first 8 happy numbers.

#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 < 50; i++)
	if (happy(i))
	std::cout << i << std::endl;
	return 0;
}

Output:

1
7
10
13
19
23
28
31
32
44
49

Alternative version without caching:

unsigned int happy_iteration(unsigned int n)
{
	unsigned int result = 0;
	while (n > 0)
	{
		unsigned int lastdig = n % 10;
		result += lastdig*lastdig;
		n /= 10;
	}
	return result;
}

bool is_happy(unsigned int n)
{
	unsigned int n2 = happy_iteration(n);
	while (n != n2)
	{
		n = happy_iteration(n);
		n2 = happy_iteration(happy_iteration(n2));
	}
	return n == 1;
}

#include <iostream>

int main()
{
	unsigned int current_number = 1;

	unsigned int happy_count = 0;
	while (happy_count != 8)
	{
		if (is_happy(current_number))
		{
			std::cout << current_number << " ";
			++happy_count;
		}
		++current_number;
	}
	std::cout << std::endl;
}

Output:

1 7 10 13 19 23 28 31

Cycle detection in is_happy() above is done using Floyd’s cycle-finding algorithm.

SOURCE

Content is available under GNU Free Documentation License 1.2.