Счастливый номер
Число называется счастливым, если оно приводит к 1 после последовательности шагов, в которой каждый номер шага заменяется суммой квадратов его цифры, то есть, если мы начинаем с счастливого числа и продолжаем заменять его суммой квадратов цифр, мы достигаем 1.
Примеры :
Ввод: n = 19 Выход: True 19 - счастливое число, 1 ^ 2 + 9 ^ 2 = 82 8 ^ 2 + 2 ^ 2 = 68 6 ^ 2 + 8 ^ 2 = 100 1 ^ 2 + 0 ^ 2 + 0 ^ 2 = 1 Когда мы достигли 1, 19 - счастливое число. Ввод: n = 20 Выход: ложь
A number will not be a Happy Number when it makes a loop in its sequence that is it touches a number in sequence which already been touched. So to check whether a number is happy or not, we can keep a set, if the same number occurs again we flag result as not happy. A simple function on the above approach can be written as below –
C++
// method return true if n is Happy Number// numSquareSum method is given in below detailed code snippetint 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); }} |
Java
// method return true if n is Happy Number// numSquareSum method is given in below detailed code snippetstatic int isHappyNumber(int n){ HashSet<Integer> 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 Princi Singh |
Javascript
<script>// method return true if n is Happy Number// numSquareSum method is given in below detailed code snippet 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> |
Мы можем решить эту проблему, не занимая лишнего места, и эту технику можно использовать и в некоторых других подобных задачах. Если мы будем рассматривать каждое число как узел, а замену цифрой квадратной суммы как ссылку, тогда эта проблема будет такой же, как поиск цикла в списке ссылок:
Итак, в качестве предлагаемого решения из приведенной выше ссылки мы будем поддерживать два числа медленными и быстрыми, оба инициализируемые с заданного числа, медленное заменяется по одному шагу за раз, а быстрое заменяется двумя шагами за раз. Если они встречаются в 1, то данное число является счастливым числом, в противном случае - нет.
Выход :
13 - счастливое число
Another approach for solving this problem using no extra space.
A number cannot be a happy number if, at any step, the sum of the square of digits obtained is a single-digit number except 1 or 7. This is because 1 and 7 are the only single-digit happy numbers. Using this information, we can develop an approach as shown in the code below –
Java
// 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) { if (n == 1 || n == 7) return true; 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; } if (sum == 1) return true; x = sum; } if(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#
// 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 falsestatic bool isHappynumber(int n){ if (n == 1 || n == 7) return true; 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; } if (sum == 1) return true; x = sum; } if (sum == 7) return true; return false;}// Driver codepublic 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 |
Javascript
<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) { if (n == 1 || n == 7) return true; 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; } if (sum == 1) return true; x = sum; } if(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
Эта статья предоставлена Уткаршем Триведи. Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью, используя write.geeksforgeeks.org, или отправить свою статью по электронной почте: deposit@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.