Честит номер
Опитайте в GfG Practice 
Едно число се нарича щастливо, ако води до 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++Java// 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 ); } }Python// 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 SinghC## 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 )JavaScript// 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Анализ на сложността:
Времева сложност: O(n*log(n)).
Помощно пространство: O(n), тъй като използва допълнителен комплект за съхранениеМожем да решим този проблем, без да използваме допълнително пространство и тази техника може да се използва и в някои други подобни проблеми. Ако третираме всяко число като възел и заместването с цифра на квадратна сума като връзка, тогава този проблем е същият като намиране на цикъл в списък с връзки :
Така че като предложено решение от връзката по-горе ще запазим две числа бавно и бързо и двете се инициализират от дадено число бавно се заменя стъпка по стъпка и бързо се заменя две стъпки наведнъж. Ако се срещнат при 1, тогава даденото число е щастливо число, в противен случай не.
C++C// C++ program to check a number is a Happy number or not #includeusing namespace std ; // Utility method to return sum of square of digit of n int numSquareSum ( int n ) { int squareSum = 0 ; while ( n ) { squareSum += ( n % 10 ) * ( n % 10 ); n /= 10 ; } return squareSum ; } // method return true if n is Happy number 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 to test above methods int main () { int n = 13 ; if ( isHappynumber ( n )) cout < < n < < ' is a Happy number n ' ; else cout < < n < < ' is not a Happy number n ' ; } // This code is contributed by divyeshrabadiya07 Java// C program to check a number is a Happy number or not #include#include // Utility method to return sum of square of digit of n int numSquareSum ( int n ) { int squareSum = 0 ; while ( n ) { squareSum += ( n % 10 ) * ( n % 10 ); n /= 10 ; } return squareSum ; } // method return true if n is Happy number 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 to test above methods int main () { int n = 13 ; if ( isHappynumber ( n )) printf ( '%d is a Happy number n ' n ); else printf ( '%d is not a Happy number n ' n ); } // This code is contributed by Sania Kumari Gupta // (kriSania804) Python// 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' ); } }C## 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' )JavaScript// 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.PHP< 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>Изход:
13 is a Happy NumberАнализ на сложността:
Времева сложност: O(n*log(n)).
Помощно пространство: О(1).C++
Друг подход за решаване на този проблем без допълнително пространство.
Едно число не може да бъде щастливо число ако на която и да е стъпка сумата от квадрата на получените цифри е едноцифрено число с изключение на 1 или 7 . Това е така, защото 1 и 7 са единствените едноцифрени щастливи числа. Използвайки тази информация, можем да разработим подход, както е показано в кода по-долу -C// C++ program to check if a number is a Happy number or // not. #includeusing namespace std ; // Method - returns true if the input is a happy number else // returns false 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 == 7 || sum == 1 ) return true ; return false ; } int main () { int n = 13 ; if ( isHappynumber ( n )) cout < < n < < ' is a Happy number' ; else cout < < n < < ' is not a Happy number' ; return 0 ; } // This code is contributed by Sania Kumari Gupta Java// C program to check if a number is a Happy number or // not. #include#include // Method - returns true if the input is a happy number else // returns false 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 == 7 || sum == 1 ) return true ; return false ; } int main () { int n = 13 ; if ( isHappynumber ( n )) printf ( '%d is a Happy number' n ); else printf ( '%d is not a Happy number' n ); return 0 ; } // This code is contributed by Sania Kumari Gupta Python// 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' ); } }C## 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.JavaScript// 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
Изход13 is a Happy numberАнализ на сложността:
Времева сложност: O(n*log(n)).
Помощно пространство: О(1).Вижте вашата статия да се появява на главната страница на GeeksforGeeks и помогнете на други маниаци.
Създаване на тест
