Skaitli sauc par laimīgu, ja tas noved pie 1 pēc soļu secības, kur katrs soļa numurs tiek aizstāts ar tā cipara kvadrātu summu, tas ir, ja mēs sākam ar laimīgo skaitli un turpinām to aizstāt ar cipariem kvadrātsummu, mēs sasniedzam 1.
Piemēri:
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
Skaitlis nebūs laimīgs skaitlis, ja tas savā secībā izveido cilpu, tas ir, tas pieskaras skaitlim pēc kārtas, kas jau ir pieskāries. Tātad, lai pārbaudītu, vai skaitlis ir laimīgs, mēs varam saglabāt kopu, ja tas pats skaitlis atkārtojas, atzīmējam rezultātu kā neapmierinošu. Vienkāršu funkciju, izmantojot iepriekš minēto pieeju, var uzrakstīt šādi -
metodes pārslodzeC++
// 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>
Sarežģītības analīze:
Laika sarežģītība: O(n*log(n)).
Palīgtelpa: O(n), jo glabāšanai tiek izmantots papildu komplekts
stīgu celtnieks
Mēs varam atrisināt šo problēmu, neizmantojot papildu vietu, un šo paņēmienu var izmantot arī dažās citās līdzīgās problēmās. Ja mēs katru skaitli traktējam kā mezglu un aizstāšanu ar kvadrātsummas ciparu kā saiti, tad šī problēma ir tāda pati kā cilpas atrašana saišu sarakstā :
Tātad, kā piedāvātais risinājums no iepriekš minētās saites, mēs saglabāsim divus skaitļus lēni un ātri, gan inicializācija no noteikta skaitļa tiek aizstāta pa vienam solim, un ātra tiek aizstāta divus soļus vienlaikus. Ja viņi satiekas 1, tad dotais skaitlis ir Happy Number, pretējā gadījumā nē.
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. ?> Izvade:
13 is a Happy NumberSarežģītības analīze:
Laika sarežģītība: O(n*log(n)).
Palīgtelpa: O(1).
Vēl viena pieeja šīs problēmas risināšanai, neizmantojot papildu vietu.
Skaitlis nevar būt laimīgs skaitlis ja jebkurā solī iegūtā ciparu kvadrāta summa ir viencipara skaitlis, izņemot 1 vai 7 . Tas ir tāpēc, ka 1 un 7 ir vienīgie viencipara laimīgie skaitļi. Izmantojot šo informāciju, mēs varam izstrādāt pieeju, kā parādīts tālāk esošajā kodā -
segmentācijas vainas kodols izmestsC++
// 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>
Izvade
13 is a Happy number
Sarežģītības analīze:
Laika sarežģītība: O(n*log(n)).
Palīgtelpa: O(1).
Skatiet savu rakstu GeeksforGeeks galvenajā lapā un palīdziet citiem Geeks.