Аз жаргалтай дугаар


Хэцүү байдлын түвшин Easy
Байнга асуудаг Adobe Амазоны Apple-ийн 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 буцах тохиолдолд 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

Аз жаргалтай дугаар

Бид энэ тоог нэг болгож бууруулах боломжтой тул аз жаргалтай тоо болно.

арга барил

Энэ асуудал нь маш энгийн бөгөөд зөвхөн багцны үндсэн ойлголтыг ашигладаг.

Олонлог гэж юу вэ?

Set бол өвөрмөц элементүүд байдаг ассоциатив сав юм.

Энэ асуудлыг шийдэхийн тулд бид багц. Багцад бид тухайн тооны цифрүүдийн квадратыг нэмсний дараа шинээр үүссэн дугаарыг оруулах болно. Хэрэв элемент нь багцад аль хэдийн орсон бол энэ нь гогцоо үүсгэж байгаа тул бид өгөгдсөн тоог нэг болгож хөрвүүлж чадахгүй тул энэ нь аз жаргалтай тоо биш юм. Хэрэв тоог нэг болгож бууруулсан бол тухайн тоо нь аз жаргалтай тоо болно.

код

Аз жаргалтай дугаарын 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), log N нь 10 дугаартай байна. Тэгэхээр цаг хугацааны нарийн төвөгтэй байдал нь тухайн тооны цифрүүдийн тооноос хамаарна. Энэ нь логарифмын хүчин зүйлээр буурсаар байна. Тиймээс цаг хугацааны нарийн төвөгтэй байдал нь O (log N) болно.

Сансрын нарийн төвөгтэй байдал

O (logN), эдгээр завсрын дугааруудыг хадгалах зай шаардагдана. Цаг хугацааны нарийн төвөгтэй адил орон зайн нарийн төвөгтэй байдал нь логарифмик шинж чанартай байдаг.