Среќен број


Ниво на тешкотија Лесно
Често прашувано во Adobe Амазон Јаболко ЈП Морган
Хаш Хашинг Математика

Изјава за проблем

Што е среќен број?

Бројот е среќен број ако можеме да го намалиме дадениот број на 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

Среќен број

Овој број можеме да го намалиме на еден, па затоа е среќен број.

Пристап

Овој проблем е многу едноставен и го користи само основниот концепт на множеството.

Што е комплет?

Set е асоцијативен контејнер во кој се присутни уникатни елементи.

За да го решиме овој проблем, ќе користиме a постави. Во комплетот, ќе го вметнеме новоформираниот број откако ќе го додадеме квадратот на цифрите на бројот. Сега, ако елементот е веќе присутен во множеството, тоа значи дека формира јамка и не можеме да го претвориме дадениот број во еден, така што ова не е среќен број. Ако бројот се намали на еден, тогаш дадениот број е среќен број.

Код

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

Јава код за среќен број

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

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

Временска комплексност

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

Комплексноста на просторот

О (најаваН), потребен е простор за зачувување на овие средни броеви. Слично на временската сложеност, вселенската комплексност е исто така логаритамска.