Skip to content

Instantly share code, notes, and snippets.

@MetroWind
Created February 23, 2022 03:46
Show Gist options
  • Save MetroWind/7a2749d9a57e7759a4702fabb348174b to your computer and use it in GitHub Desktop.
Save MetroWind/7a2749d9a57e7759a4702fabb348174b to your computer and use it in GitHub Desktop.
Check if a number is a “happy number”, constant-space algorithm, with visualization of the algorithm. (https://en.wikipedia.org/wiki/Happy_number)
#include <iostream>
#include <vector>
#include <iomanip>
int sumSqDigits(int n)
{
int result = 0;
while(n > 0)
{
int digit = n % 10;
result += digit * digit;
n /= 10;
}
return result;
}
class HappyPointer
{
public:
HappyPointer() = default;
HappyPointer(int initial, size_t index) : n(initial), i(index) {}
HappyPointer& advance()
{
n = sumSqDigits(n);
i++;
return *this;
}
int n;
size_t i;
};
class Happy
{
public:
Happy(int n) : initial(n), history(1, n) {}
bool isHappy()
{
slow = HappyPointer(initial, 0);
fast = HappyPointer(initial, 0);
fast.advance();
while(true)
{
expandHistory();
print();
if(slow.n == 1 || fast.n == 1)
{
return true;
}
if(slow.n == fast.n)
{
return false;
}
slow.advance();
fast.advance();
expandHistory();
fast.advance();
}
}
private:
void print() const
{
for(size_t i = 0; i < history.size(); i++)
{
std::cout << std::setw(3) << history[i];
if (i != history.size() - 1)
{
std::cout << " -> ";
}
}
std::cout << std::endl;
std::cout << std::string(slow.i * 7, ' ') << "^";
std::cout << std::string((fast.i - slow.i) * 7, ' ') << "*";
std::cout << std::endl;
}
void expandHistory()
{
if(fast.i >= history.size())
{
history.resize(fast.i + 1);
}
history[slow.i] = slow.n;
history[fast.i] = fast.n;
}
int initial;
std::vector<int> history;
HappyPointer slow;
HappyPointer fast;
};
int main()
{
Happy h(8);
std::cout << h.isHappy() << std::endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment