Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

feat: add happy number#364

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Merged
MoigeMatino merged 2 commits intomainfromhappy-number
Oct 28, 2024
Merged
Show file tree
Hide file tree
Changes fromall commits
Commits
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
65 changes: 65 additions & 0 deletionsarrays_and_strings/happy_number/README.md
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
## **Problem Statement**

Write an algorithm to determine if a number `n` is a happy number.

We use the following process to check if a given number is a happy number:

- Starting with the given number n, replace the number with the sum of the squares of its digits.
- Repeat the process until:
- The number equals 1, which will depict that the given number n is a happy number.
- It enters a cycle, which will depict that the given number n is not a happy number.

Return TRUE if `n` is a happy number, and FALSE if not.

### Constraints

> 1 ≤ n ≤ 2<sup>31</sup> - 1

## **Examples**

### Example 1: Determining a Happy Number

**Input:** `n = 19`

**Process:**

1. Start with `n = 19`.
2. Calculate the sum of the squares of its digits: $1^2 + 9^2 = 1 + 81 = 82$.
3. Replace 19 with 82.
4. Calculate the sum of the squares of the digits of 82: $8^2 + 2^2 = 64 + 4 = 68$.
5. Replace 82 with 68.
6. Calculate the sum of the squares of the digits of 68: $6^2 + 8^2 = 36 + 64 = 100$.
7. Replace 68 with 100.
8. Calculate the sum of the squares of the digits of 100: $1^2 + 0^2 + 0^2 = 1 + 0 + 0 = 1$.

Since the process reaches 1, **19 is a happy number**.

**Output:** `TRUE`

### Example 2: Determining a Non-Happy Number

**Input:** `n = 20`

**Process:**

1. Start with `n = 20`.
2. Calculate the sum of the squares of its digits: $2^2 + 0^2 = 4 + 0 = 4$.
3. Replace 20 with 4.
4. Calculate the sum of the squares of the digits of 4: $4^2 = 16$.
5. Replace 4 with 16.
6. Calculate the sum of the squares of the digits of 16: $1^2 + 6^2 = 1 + 36 = 37$.
7. Replace 16 with 37.
8. Calculate the sum of the squares of the digits of 37: $3^2 + 7^2 = 9 + 49 = 58$.
9. Replace 37 with 58.
10. Calculate the sum of the squares of the digits of 58: $5^2 + 8^2 = 25 + 64 = 89$.
11. Replace 58 with 89.
12. Calculate the sum of the squares of the digits of 89: $8^2 + 9^2 = 64 + 81 = 145$.
13. Replace 89 with 145.
14. Calculate the sum of the squares of the digits of 145: $1^2 + 4^2 + 5^2 = 1 + 16 + 25 = 42$.
15. Replace 145 with 42.
16. Calculate the sum of the squares of the digits of 42: $4^2 + 2^2 = 16 + 4 = 20$.

The process returns to 20, indicating a cycle. **20 is not a happy number**.

**Output:** `FALSE`

View file
Open in desktop
Empty file.
57 changes: 57 additions & 0 deletionsarrays_and_strings/happy_number/happy_number.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
def happy_number(n: int) -> bool:
"""
Determine if a number is a happy number.

A happy number is defined as a number which eventually reaches 1 when replaced by the sum of the square of each digit.
If it loops endlessly in a cycle that does not include 1, it is not a happy number.

Parameters:
n (int): The number to be checked.

Returns:
bool: True if the number is a happy number, False otherwise.

"""
slow = n
fast = squared_digits_sum(n)

while fast != slow:
slow = squared_digits_sum(slow)
fast = squared_digits_sum(squared_digits_sum(fast))

return slow == 1

def squared_digits_sum(n: int) -> int:
"""
Calculate the sum of the squares of the digits of a number.

Parameters:
n (int): The number whose digits are to be squared and summed.

Returns:
int: The sum of the squares of the digits of the number.
"""
digits_sum = 0
while n > 0:
n, digit = divmod(n, 10)
digits_squared = digit * digit
digits_sum += digits_squared
return digits_sum

# Approach and Reasoning:
# -----------------------
# - The function uses Floyd's Cycle Detection Algorithm (also known as the tortoise and hare algorithm) to detect cycles. Also known as fast and slow pointers.
# - Two pointers, `slow` and `fast`, are used to traverse the sequence of numbers generated by repeatedly replacing the number with the sum of the squares of its digits.
# - `slow` moves one step at a time (computes the sum of squares once), while `fast` moves two steps at a time (computes the sum of squares twice).
# - If there is a cycle (i.e., the number is not happy), `slow` and `fast` will eventually meet at the same number.
# - If the number is happy, the sequence will eventually reach 1, and the loop will terminate.

# Time Complexity:
# ----------------
# - The time complexity is O(log n), where n is the input number.
# - The time complexity is O(log_{10}(n)), where n is the input number. This complexity arises from the `squared_digits_sum` function,
# as the number of digits in n is proportional to log_{10}(n), and each digit is processed in constant time.

# Space Complexity:
# -----------------
# - The space complexity is O(1) because only a constant amount of extra space is used for variables and function calls.
[8]ページ先頭
©2009-2025 Movatter.jp