Бақытты нөмір


Күрделілік дәрежесі оңай
Жиі кіреді Adobe Amazon алма 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-ге дейін азайса, true қайтарылады, әйтпесе жалған қайтарылады.

мысал

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 ++ коды

#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 коды

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), журналдың N базасы бар. Демек, уақыттың күрделілігі сандағы цифрлардың санына тәуелді. Логарифмдік коэффициентпен ол азая береді. Сонымен уақыттың күрделілігі O (журнал N) болады.

Ғарыштың күрделілігі

O (logN), осы аралық сандарды сақтау үшін орын қажет. Уақыттың күрделілігіне ұқсас кеңістіктің күрделілігі де логарифмикалық.