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


Сложный уровень Легко
Часто спрашивают в саман Амазонка Apple JP Morgan
Hash хеширования Экзамен Математики

Постановка задачи

Что такое счастливое число?

Число является счастливым числом, если мы можем уменьшить данное число до 1, следуя этому процессу:

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

Это означает, что цикл формируется так, как если бы мы начали с числа, следили за процессом, чтобы преобразовать его в единицу, но мы достигли числа, с которым смотрели, тогда мы говорим, что это формирует цикл.

Пример цикла формирования числа выглядит следующим образом:

89
8*8+9*9=145
1*1*+4*4+5*5=42
4*4+2*2=20
2*2+0*0=4
4*4=16
1*1+6*6=37
3*3+7*7=58
5*5+8*8=89

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

Пример

19
true

объяснение

1^2+9^2=82

8^2+2^2=68

6^2+8^2=100

1^2+0^2+0^2=1

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

Мы можем уменьшить это число до одного, так что это будет счастливое число.

Подход

Эта задача очень проста и использует только базовую концепцию набора.

Что такое набор?

Набор - это ассоциативный контейнер, в котором присутствуют уникальные элементы.

Для решения этой проблемы мы будем использовать задавать. В набор мы вставим вновь образованное число после сложения квадрата цифр числа. Теперь, если элемент уже присутствует в наборе, это означает, что он формирует цикл, и мы не можем преобразовать данное число в одно, так что это не удачное число. Если число уменьшается до единицы, то данное число является счастливым числом.

Код:

Код C ++ для Happy Number

#include <bits/stdc++.h> 
using namespace std; 

 bool isHappy(int n) {
        unordered_set<int> tmp;
        while(n != 1)
        {
            if(tmp.find(n) == tmp.end())
                tmp.insert(n);
            else
                return false;
            int sum = 0;
            while(n != 0)
            {
                sum += pow(n % 10,2);
                n = n / 10;
            }
            n = sum;
        }
        return true;
    }

int main() 
{ 
    int n=19;
    int answer=isHappy(n);
    if(answer)
    cout<<"true"<<endl;
    else
    cout<<"false"<<endl;
  return 0; 
}
true

Код Java для Happy Number

import java.util.*;

class Main
{
  static public boolean isHappy(int n) {
      Set<Integer> inLoop = new HashSet<Integer>();
      int squareSum,remain;
      while (inLoop.add(n)) {
      	squareSum = 0;
        while (n > 0) {
            remain = n%10;
          squareSum += remain*remain;
          n /= 10;
        }
        if (squareSum == 1)
          return true;
        else
          n = squareSum;
    }
    return false;
  }

  public static void main (String[] args) throws java.lang.Exception
  {
    int n = 19;
    boolean result = isHappy(n);
    System.out.print(result);
  }
}
19
true

Анализ сложности

Сложность времени

O (журнал N), log N имеет основание 10. Таким образом, временная сложность зависит от количества цифр в числе. И продолжает уменьшаться с логарифмическим множителем. Таким образом, временная сложность равна O (log N).

Космическая сложность

O (logN), требуется место для хранения этих промежуточных чисел. Подобно временной сложности, пространственная сложность также является логарифмической.