Рубрики

Счастливый номер

Число называется счастливым, если оно приводит к 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

Число не будет счастливым числом, когда оно делает цикл в своей последовательности, то есть касается числа в последовательности, которое уже было затронуто. Таким образом, чтобы проверить, является ли число счастливым или нет, мы можем сохранить набор, если тот же номер встречается снова, мы отмечаем результат как неудовлетворительный. Простая функция на подходе выше может быть написана как ниже —

// метод возвращает истину, если n - счастливый номер
// метод numSquareSum приведен ниже в подробном фрагменте кода

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);

    }

}

Мы можем решить эту проблему, не используя дополнительное пространство, и эту технику можно использовать и в некоторых других подобных задачах. Если мы будем рассматривать каждое число как узел, а замену цифрой с квадратной суммой — как ссылку, то эта проблема аналогична поиску цикла в списке ссылок :

Таким образом, в качестве предлагаемого решения из вышеупомянутой ссылки, мы будем держать два числа медленными и быстрыми, и оба инициализировать из данного числа, медленное заменяется одним шагом за раз, а быстрое — двумя шагами за раз. Если они встречаются в 1, то данное число является счастливым числом, иначе нет.

C ++

// C / C ++ программа для проверки номера Happy
// номер или нет
#include <bits/stdc++.h>

using namespace std;

  
// Служебный метод для возврата суммы квадрата
// цифра n

int numSquareSum(int n)

{

    int squareSum = 0;

    while (n)

    {

        squareSum += (n % 10) * (n % 10);

        n /= 10;

    }

    return squareSum;

}

  
// метод возвращает true, если n - это счастливое число

bool isHappynumber(int n)

{

    int slow, fast;

  

    // инициализируем медленно и быстро

    slow = fast = n;

    do

    {

        // переместить медленное число на одну итерацию

        slow = numSquareSum(slow);

  

        // переместить быстрое число на две итерации

        fast = numSquareSum(numSquareSum(fast));

  

    }

    while (slow != fast);

  

    // если оба числа встречаются в 1, то возвращаем true

    return (slow == 1);

}

  
// Код драйвера для тестирования вышеуказанных методов

int main()

{

    int n = 13;

    if (isHappynumber(n))

        cout << n << " is a Happy number\n";

    else

        cout << n << " is not a Happy number\n";

}

Джава

// Java-программа для проверки номера Happy
// номер или нет

  

class GFG {

   
// Служебный метод для возврата суммы квадрата
// цифра n

static int numSquareSum(int n)

{

    int squareSum = 0;

    while (n!= 0)

    {

        squareSum += (n % 10) * (n % 10);

        n /= 10;

    }

    return squareSum;

}

   
// метод возвращает true, если n - это счастливое число

static boolean isHappynumber(int n)

{

    int slow, fast;

   

    // инициализируем медленно и быстро

    slow = fast = n;

    do

    {

        // перемещаем медленное число

        // за одну итерацию

        slow = numSquareSum(slow);

   

        // переместить быстрый номер

        // на две итерации

        fast = numSquareSum(numSquareSum(fast));

   

    }

    while (slow != fast);

   

    // если оба числа встречаются в 1,

    // затем возвращаем true

    return (slow == 1);

}

   
// Код драйвера для тестирования вышеуказанных методов

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

# Python3 программа для проверки номера
# это счастливый номер или нет

  
# Сервисный метод для возврата
# сумма квадрата цифры n

def numSquareSum(n):

    squareSum = 0;

    while(n):

        squareSum += (n % 10) * (n % 10);

        n = int(n / 10);

    return squareSum;

  
# метод возвращает true, если
# n - это счастливый номер

def isHappynumber(n):

  

    # инициализировать медленно

    # и быстро

    slow = n;

    fast = n;

    while(True):

          

        # двигаться медленное число

        # за одну итерацию

        slow = numSquareSum(slow);

  

        # переместить быстрый номер

        # на две итерации

        fast = numSquareSum(numSquareSum(fast));

        if(slow != fast):

            continue;

        else:

            break;

  

    # если оба числа встречаются в 1,

    # затем верните true

    return (slow == 1);

  
Код водителя

n = 13;

if (isHappynumber(n)):

    print(n , "is a Happy number");

else:

    print(n , "is not a Happy number");

  
# Этот код предоставлен mits

C #

// C # программа для проверки номера
// Счастливое число или нет

using System;

class GFG {

  
// Сервисный метод для возврата
// сумма квадрата цифры n

static int numSquareSum(int n)

{

    int squareSum = 0;

    while (n!= 0)

    {

        squareSum += (n % 10) * 

                     (n % 10);

        n /= 10;

    }

    return squareSum;

}

  
// метод возвращает true, если
// n счастливое число

static bool isHappynumber(int n)

{

    int slow, fast;

  

    // инициализируем медленно и

    // быстро

    slow = fast = n;

    do

    {

          

        // перемещаем медленное число

        // за одну итерацию

        slow = numSquareSum(slow);

  

        // переместить быстрый номер

        // на две итерации

        fast = numSquareSum(numSquareSum(fast));

  

    }

    while (slow != fast);

  

    // если оба числа встречаются в 1,

    // затем возвращаем true

    return (slow == 1);

}

  
// Код драйвера

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");

}
}

  
// Этот код предоставлен anuj_67.

PHP

<?php
// PHP программа для проверки номера
// Счастливое число или нет

  
// Сервисный метод для возврата
// сумма квадрата цифры n

function numSquareSum( $n)

{

    $squareSum = 0;

    while ($n)

    {

        $squareSum += ($n % 10) * 

                      ($n % 10);

        $n /= 10;

    }

    return $squareSum;

}

  
// метод возвращает true, если
// n счастливое число

function isHappynumber( $n)

{

    $slow; $fast;

  

    // инициализируем медленный

    // и быстро

    $slow = $n;

    $fast = $n;

    do

    {

        // перемещаем медленное число

        // за одну итерацию

        $slow = numSquareSum($slow);

  

        // переместить быстрый номер

        // на две итерации

        $fast = numSquareSum(numSquareSum($fast));

  

    }

    while ($slow != $fast);

  

    // если оба числа встречаются в 1,

    // затем возвращаем true

    return ($slow == 1);

}

  
// Код драйвера

$n = 13;

if (isHappynumber($n))

    echo $n , " is a Happy number\n";

else

    echo n , " is not a Happy number\n";

  
// Этот код предоставлен anuj_67.
?>


Выход :

13 is a Happy Number

Эта статья предоставлена Уткаршем Триведи . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Счастливый номер

0.00 (0%) 0 votes