ハッピーナンバー
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)余分なスペースを使用せずにこの問題を解決でき、そのテクニックは他の同様の問題にも使用できます。すべての数値をノードとして扱い、二乗和の数字による置換をリンクとして扱う場合、この問題は次と同じになります。 リンクリスト内のループを見つける :
したがって、上記のリンクから提案される解決策として、2 つの数値を低速と高速に保ち、両方とも指定された数値から初期化します。低速は一度に 1 ステップずつ置き換えられ、高速は一度に 2 ステップずつ置き換えられます。それらが 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 桁の数値である場合 。なぜなら、1桁の幸せな数字は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 のメイン ページにあなたの記事が掲載されているのを見て、他のオタクを助けてください。
クイズの作成
