Ուրախ համար


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Adobe Amazon խնձոր JP Morgan
Խանգարել Հեշինգ Մաթեմատիկա

Խնդիրի հայտարարություն

Ի՞նչ է ուրախ թիվը:

Թիվը երջանիկ թիվ է, եթե այս գործընթացին հաջորդող տվյալ թիվը կարողանանք 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 ++ կոդը 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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (տեղեկամատյան N), log N- ն ունի հիմք 10: Այսպիսով, ժամանակի բարդությունը կախված է համարի թվանշանների քանակից: Եվ դա շարունակում է նվազել լոգարիթմական գործոնի հետ միասին: Այսպիսով, ժամանակի բարդությունը O է (մուտքագրում N):

Տիեզերական բարդություն

O (logN), տարածություն է պահանջվում այս միջանկյալ համարները պահելու համար: Theամանակի բարդության նման, տարածության բարդությունը նույնպես լոգարիթմիկ է: