Non-Cyclical Numbers
Exploring Non-Cyclical Numbers: A Step-by-Step Guide
In mathematics and computer science, certain problems help us uncover patterns within numbers. One such intriguing concept is non-cyclical numbers, also known as “happy numbers.”
In this article, we’ll explore what makes a number non-cyclical, understand its algorithm, and implement an efficient solution.
What is a Non-Cyclical Number?
A non-cyclical number is defined by an iterative process where you repeatedly replace a number with the sum of the squares of its digits. The process ends in one of two ways:
- The number eventually equals 1 (making it a non-cyclical number).
- The number falls into a repetitive cycle that does not include 1.
If the process stops at 1, the number is classified as non-cyclical. Otherwise, it is cyclical.
Problem Statement
Given a positive integer n, determine whether it is a non-cyclical number.
Constraints:
- 1 <= n <= 1000
Example 1
Input: n = 100
Output: true
Explanation: 1^2 + 0^2 + 0^2 = 1
Example 2
Input: n = 101
Output: false
Explanation:
Explanation:
1^2 + 0^2 + 1^2 = 2
2^2 = 4
4^2 = 16
1^2 + 6^2 = 37
3^2 + 7^2 = 58
5^2 + 8^2 = 89
8^2 + 9^2 = 145
1^2 + 4^2 + 5^2 = 42
4^2 + 2^2 = 20
2^2 + 0^2 = 4 (This number has already been seen)
Approach to Solve the Problem
To determine whether a number is non-cyclical, we must repeatedly calculate the sum of the squares of its digits. During this process, we need to:
- Stop if we reach the number 1.
- Detect cycles by keeping track of previously encountered numbers.
Algorithm
- Define a helper function
sum_of_squaresthat calculates the sum of the squares of the digits of a number. - Use a set to store numbers that have already been seen.
- Loop until:
- The number equals 1 (return
true). - A previously seen number is encountered (return
false).
- The number equals 1 (return
There are mainly three approach to solve this problem –
- Hash Set
- Fast And Slow Pointers – I
- Fast And Slow Pointers – II
1. Hash Set
- Time complexity: O(logn)
- Space complexity: O(logn)
Python
C++
Java
JavaScript
Python
class Solution:
def isHappy(self, n: int) -> bool:
visit = set()
while n not in visit:
visit.add(n)
n = self.sumOfSquares(n)
if n == 1:
return True
return False
def sumOfSquares(self, n: int) -> int:
output = 0
while n:
digit = n % 10
digit = digit ** 2
output += digit
n = n // 10
return output
C++
class Solution {
public:
bool isHappy(int n) {
unordered_set visit;
while (visit.find(n) == visit.end()) {
visit.insert(n);
n = sumOfSquares(n);
if (n == 1) {
return true;
}
}
return false;
}
private:
int sumOfSquares(int n) {
int output = 0;
while (n > 0) {
int digit = n % 10;
digit = digit * digit;
output += digit;
n /= 10;
}
return output;
}
};
Java
public class Solution {
public boolean isHappy(int n) {
Set visit = new HashSet<>();
while (!visit.contains(n)) {
visit.add(n);
n = sumOfSquares(n);
if (n == 1) {
return true;
}
}
return false;
}
private int sumOfSquares(int n) {
int output = 0;
while (n > 0) {
int digit = n % 10;
digit = digit * digit;
output += digit;
n /= 10;
}
return output;
}
}
JavaScript
class Solution {
/**
* @param {number} n
* @return {boolean}
*/
isHappy(n) {
const visit = new Set();
while (!visit.has(n)) {
visit.add(n);
n = this.sumOfSquares(n);
if (n === 1) {
return true;
}
}
return false;
}
/**
* @param {number} n
* @return {number}
*/
sumOfSquares(n) {
let output = 0;
while (n > 0) {
let digit = n % 10;
digit = digit * digit;
output += digit;
n = Math.floor(n / 10);
}
return output;
}
}
2. Fast And Slow Pointers – I
Time & Space Complexity
- Time complexity: O(logn)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
bool isHappy(int n) {
int slow = n, fast = sumOfSquares(n);
while (slow != fast) {
fast = sumOfSquares(fast);
fast = sumOfSquares(fast);
slow = sumOfSquares(slow);
}
return fast == 1;
}
private:
int sumOfSquares(int n) {
int output = 0;
while (n != 0) {
output += (n % 10) * (n % 10);
n /= 10;
}
return output;
}
};
Java
public class Solution {
public boolean isHappy(int n) {
int slow = n, fast = sumOfSquares(n);
while (slow != fast) {
fast = sumOfSquares(fast);
fast = sumOfSquares(fast);
slow = sumOfSquares(slow);
}
return fast == 1;
}
private int sumOfSquares(int n) {
int output = 0;
while (n != 0) {
output += (n % 10) * (n % 10);
n /= 10;
}
return output;
}
}
Python
class Solution:
def isHappy(self, n: int) -> bool:
slow, fast = n, self.sumOfSquares(n)
while slow != fast:
fast = self.sumOfSquares(fast)
fast = self.sumOfSquares(fast)
slow = self.sumOfSquares(slow)
return True if fast == 1 else False
def sumOfSquares(self, n: int) -> int:
output = 0
while n:
digit = n % 10
digit = digit ** 2
output += digit
n = n // 10
return outputJavaScript
class Solution {
/**
* @param {number} n
* @return {boolean}
*/
isHappy(n) {
let slow = n;
let fast = this.sumOfSquares(n);
while (slow !== fast) {
fast = this.sumOfSquares(fast);
fast = this.sumOfSquares(fast);
slow = this.sumOfSquares(slow);
}
return fast === 1;
}
/**
* @param {number} n
* @return {number}
*/
sumOfSquares(n) {
let output = 0;
while (n !== 0) {
output += (n % 10) ** 2;
n = Math.floor(n / 10);
}
return output;
}
}3. Fast And Slow Pointers – II
- Time complexity: O(logn)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
bool isHappy(int n) {
int slow = n, fast = sumOfSquares(n);
int power = 1, lam = 1;
while (slow != fast) {
if (power == lam) {
slow = fast;
power *= 2;
lam = 0;
}
lam++;
fast = sumOfSquares(fast);
}
return fast == 1;
}
private:
int sumOfSquares(int n) {
int output = 0;
while (n != 0) {
output += (n % 10) * (n % 10);
n /= 10;
}
return output;
}
};
Java
public class Solution {
public boolean isHappy(int n) {
int slow = n, fast = sumOfSquares(n);
int power = 1, lam = 1;
while (slow != fast) {
if (power == lam) {
slow = fast;
power *= 2;
lam = 0;
}
lam++;
fast = sumOfSquares(fast);
}
return fast == 1;
}
private int sumOfSquares(int n) {
int output = 0;
while (n != 0) {
output += (n % 10) * (n % 10);
n /= 10;
}
return output;
}
}
Python
class Solution:
def isHappy(self, n: int) -> bool:
slow, fast = n, self.sumOfSquares(n)
power = lam = 1
while slow != fast:
if power == lam:
slow = fast
power *= 2
lam = 0
fast = self.sumOfSquares(fast)
lam += 1
return True if fast == 1 else False
def sumOfSquares(self, n: int) -> int:
output = 0
while n:
digit = n % 10
digit = digit ** 2
output += digit
n = n // 10
return outputJavaScript
class Solution {
/**
* @param {number} n
* @return {boolean}
*/
isHappy(n) {
let slow = n;
let fast = this.sumOfSquares(n);
let power = 1, lam = 1;
while (slow !== fast) {
if (power === lam) {
slow = fast;
power *= 2;
lam = 0;
}
lam++;
fast = this.sumOfSquares(fast);
}
return fast === 1;
}
/**
* @param {number} n
* @return {number}
*/
sumOfSquares(n) {
let output = 0;
while (n !== 0) {
output += (n % 10) ** 2;
n = Math.floor(n / 10);
}
return output;
}
}
