Едно число се нарича щастливо, ако води до 1 след поредица от стъпки, при което номерът на всяка стъпка се заменя със сумата от квадратите на неговата цифра, т.е. ако започнем с щастливо число и продължаваме да го заместваме с квадратна сума от цифри, достигаме 1.
Примери:
Input: n = 19
Output: True
19 is Happy Number
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
As we reached to 1 19 is a Happy Number.
Input: n = 20
Output: False
Едно число няма да бъде щастливо число, когато прави цикъл в своята последователност, т.е. докосва число в последователност, която вече е била докосната. Така че, за да проверим дали едно число е щастливо или не, можем да запазим набор, ако същото число се появи отново, маркираме резултата като недоволен. Една проста функция на горния подход може да бъде написана по-долу –
работа с компютърC++
// method return true if n is Happy Number int numSquareSum(int n) { int num = 0; while (n != 0) { int digit = n % 10; num += digit * digit; n /= 10; } return num; } int isHappyNumber(int n) { set<int> st; while (1) { n = numSquareSum(n); if (n == 1) return true; if (st.find(n) != st.end()) return false; st.insert(n); } }
// method return true if n is Happy Number public static int numSquareSum(int n) { int num = 0; while (n != 0) { int digit = n % 10; num += digit * digit; n /= 10; } return num; } static boolean isHappyNumber(int n) { HashSet<Integer> st = new HashSet<>(); while (true) { n = numSquareSum(n); if (n == 1) return true; if (st.contains(n)) return false; st.add(n); } } // This code is contributed by Princi Singh
# method return true if n is Happy Number def numSquareSum(n): num = 0 while(n): digit = n % 10 num = num + digit*digit n = n // 10 return num def isHappyNumber(n): st = set() while (1): n = numSquareSum(n) if (n == 1): return True if n not in st: return False st.insert(n)
// Method return true if n is Happy Number static int numSquareSum(int n) { int num = 0; while (n != 0) { int digit = n % 10; num += digit * digit; n /= 10; } return num; } static int isHappyNumber(int n) { HashSet<int> st = new HashSet<>(); while (1) { n = numSquareSum(n); if (n == 1) return true; if (st.Contains(n)) return false; st.Add(n); } } // This code is contributed by 29AjayKumar
<script> // method return true if n is Happy Number function numSquareSum(n) { let num = 0; while (n !== 0) { let digit = n % 10; num += digit * digit; n = Math.floor(n / 10); } return num; } let st = new Set(); while (1) { n = numSquareSum(n); if (n == 1) return true; if (st.has(n)) return false; st.add(n); } } //This code is contributed by Mayank Tyagi </script>
Анализ на сложността:
Времева сложност: O(n*log(n)).
Помощно пространство: O(n), тъй като използва допълнителен комплект за съхранение
създаване на изпълним скрипт на shell
Можем да решим този проблем, без да използваме допълнително пространство и тази техника може да се използва и в някои други подобни проблеми. Ако третираме всяко число като възел и заместването с цифра на квадратна сума като връзка, тогава този проблем е същият като намиране на цикъл в списък с връзки :
Така че като предложено решение от връзката по-горе ще запазим две числа бавно и бързо и двете се инициализират от дадено число бавно се заменя стъпка по стъпка и бързо се заменя две стъпки наведнъж. Ако се срещнат при 1, тогава даденото число е щастливо число, в противен случай не.
C++// C++ program to check a number is a Happy number or not #include
// C program to check a number is a Happy number or not #include
// Java program to check a number is a Happy // number or not class GFG { // Utility method to return sum of square of // digit of n static int numSquareSum(int n) { int squareSum = 0; while (n!= 0) { squareSum += (n % 10) * (n % 10); n /= 10; } return squareSum; } // method return true if n is Happy number static boolean isHappynumber(int n) { int slow fast; // initialize slow and fast by n slow = fast = n; do { // move slow number // by one iteration slow = numSquareSum(slow); // move fast number // by two iteration fast = numSquareSum(numSquareSum(fast)); } while (slow != fast); // if both number meet at 1 // then return true return (slow == 1); } // Driver code to test above methods public static void main(String[] args) { int n = 13; if (isHappynumber(n)) System.out.println(n + ' is a Happy number'); else System.out.println(n + ' is not a Happy number'); } }
# Python3 program to check if a number is a Happy number or not # Utility method to return the sum of squares of digits of n def num_square_sum(n): square_sum = 0 while n: square_sum += (n % 10) ** 2 n //= 10 return square_sum # Method returns True if n is a Happy number def is_happy_number(n): # Initialize slow and fast pointers slow = n fast = n while True: # Move slow pointer by one iteration slow = num_square_sum(slow) # Move fast pointer by two iterations fast = num_square_sum(num_square_sum(fast)) if slow != fast: continue else: break # If both pointers meet at 1 then return True return slow == 1 # Driver Code n = 13 if is_happy_number(n): print(n 'is a Happy number') else: print(n 'is not a Happy number')
// C# program to check a number // is a Happy number or not using System; class GFG { // Utility method to return // sum of square of digit of n static int numSquareSum(int n) { int squareSum = 0; while (n!= 0) { squareSum += (n % 10) * (n % 10); n /= 10; } return squareSum; } // method return true if // n is Happy number static bool isHappynumber(int n) { int slow fast; // initialize slow and // fast by n slow = fast = n; do { // move slow number // by one iteration slow = numSquareSum(slow); // move fast number // by two iteration fast = numSquareSum(numSquareSum(fast)); } while (slow != fast); // if both number meet at 1 // then return true return (slow == 1); } // Driver code public static void Main() { int n = 13; if (isHappynumber(n)) Console.WriteLine(n + ' is a Happy number'); else Console.WriteLine(n + ' is not a Happy number'); } } // This code is contributed by anuj_67.
<script> // Javascript program to check a number is a Happy // number or not // Utility method to return sum of square of // digit of n function numSquareSum(n) { var squareSum = 0; while (n!= 0) { squareSum += (n % 10) * (n % 10); n = parseInt(n/10); } return squareSum; } // method return true if n is Happy number function isHappynumber(n) { var slow fast; // initialize slow and fast by n slow = fast = n; do { // move slow number // by one iteration slow = numSquareSum(slow); // move fast number // by two iteration fast = numSquareSum(numSquareSum(fast)); } while (slow != fast); // if both number meet at 1 // then return true return (slow == 1); } // Driver code to test above methods var n = 13; if (isHappynumber(n)) document.write(n + ' is a Happy number'); else document.write(n + ' is not a Happy number'); // This code contributed by Princi Singh </script>
// PHP program to check a number // is a Happy number or not // Utility method to return // sum of square of digit of n function numSquareSum( $n) { $squareSum = 0; while ($n) { $squareSum += ($n % 10) * ($n % 10); $n /= 10; } return $squareSum; } // method return true if // n is Happy number function isHappynumber( $n) { $slow; $fast; // initialize slow // and fast by n $slow = $n; $fast = $n; do { // move slow number // by one iteration $slow = numSquareSum($slow); // move fast number // by two iteration $fast = numSquareSum(numSquareSum($fast)); } while ($slow != $fast); // if both number meet at 1 // then return true return ($slow == 1); } // Driver Code $n = 13; if (isHappynumber($n)) echo $n ' is a Happy numbern'; else echo n ' is not a Happy numbern'; // This code is contributed by anuj_67. ?> Изход:
13 is a Happy NumberАнализ на сложността:
Времева сложност: O(n*log(n)).
Помощно пространство: О(1).
eol в python
Друг подход за решаване на този проблем без допълнително пространство.
Едно число не може да бъде щастливо число ако на която и да е стъпка сумата от квадрата на получените цифри е едноцифрено число с изключение на 1 или 7 . Това е така, защото 1 и 7 са единствените едноцифрени щастливи числа. Използвайки тази информация, можем да разработим подход, както е показано в кода по-долу -
// C++ program to check if a number is a Happy number or // not. #include
// C program to check if a number is a Happy number or // not. #include
// This code is contributed by Vansh Sodhi. // Java program to check if a number is a Happy number or // not. class GFG { // method - returns true if the input is a happy // number else returns false static boolean isHappynumber(int n) { int sum = n x = n; // this loop executes till the sum of square of // digits obtained is not a single digit number while (sum > 9) { sum = 0; // this loop finds the sum of square of digits while (x > 0) { int d = x % 10; sum += d * d; x /= 10; } x = sum; } if (sum == 1 || sum == 7) return true; return false; } // Driver code public static void main(String[] args) { int n = 13; if (isHappynumber(n)) System.out.println(n + ' is a Happy number'); else System.out.println(n + ' is not a Happy number'); } }
# Python3 program to check if a number is a Happy number or not. # Method - returns true if the input is # a happy number else returns false def isHappynumber(n): Sum x = n n # This loop executes till the sum # of square of digits obtained is # not a single digit number while Sum > 9: Sum = 0 # This loop finds the sum of # square of digits while x > 0: d = x % 10 Sum += d * d x = int(x / 10) x = Sum if Sum == 1 or Sum == 7: return True return False n = 13 if isHappynumber(n): print(n 'is a Happy number') else: print(n 'is not a Happy number') # This code is contributed by mukesh07.
// C# program to check if a number // is a Happy number or not. using System; class GFG { // Method - returns true if the input is // a happy number else returns false static bool isHappynumber(int n) { int sum = n x = n; // This loop executes till the sum // of square of digits obtained is // not a single digit number while (sum > 9) { sum = 0; // This loop finds the sum of // square of digits while (x > 0) { int d = x % 10; sum += d * d; x /= 10; } x = sum; } if (sum == 1 || sum == 7) return true; return false; } // Driver code public static void Main(String[] args) { int n = 13; if (isHappynumber(n)) Console.WriteLine(n + ' is a Happy number'); else Console.WriteLine(n + ' is not a Happy number'); } } // This code is contributed by 29AjayKumar
<script> // This code is contributed by Vansh Sodhi. // javascript program to check if a number is a Happy number or not. // method - returns true if the input is a happy // number else returns false function isHappynumber(n) { var sum = n x = n; // this loop executes till the sum of square of // digits obtained is not a single digit number while(sum > 9) { sum = 0; // this loop finds the sum of square of digits while (x > 0) { var d = x % 10; sum += d * d; x /= 10; } x = sum; } if(sum == 1 || sum == 7) return true; return false; } // Driver code var n = 13; if (isHappynumber(n)) document.write(n + ' is a Happy number'); else document.write(n + ' is not a Happy number'); // This code is contributed by 29AjayKumar </script>
Изход
13 is a Happy number
Анализ на сложността:
Времева сложност: O(n*log(n)).
Помощно пространство: О(1).
Вижте вашата статия да се появява на главната страница на GeeksforGeeks и помогнете на други маниаци.