መልካም ቁጥር


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ የ 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

መልካም ቁጥር

ይህንን ቁጥር ወደ አንድ መቀነስ እንችላለን ስለሆነም ደስተኛ ቁጥር ነው ፡፡

ቀረበ

ይህ ችግር በጣም ቀላል እና የሚያገለግለው የስብስቡን መሠረታዊ ፅንሰ-ሀሳብ ብቻ ነው ፡፡

ስብስብ ምንድን ነው?

ስብስብ ልዩ ንጥረ ነገሮች የሚገኙበት ተባባሪ መያዣ ነው ፡፡

ይህንን ችግር ለመፍታት ሀ ስብስብ. በስብስቡ ውስጥ የቁጥሩን አሃዞች ካሬ ካከሉ በኋላ አዲስ የተፈጠረውን ቁጥር እናስገባለን ፡፡ አሁን ንጥረ ነገሩ በስብስቡ ውስጥ ካለ ይህ ማለት ቀለበት እየሰራ ነው ማለት ነው እናም የተሰጠውን ቁጥር ወደ አንድ መለወጥ አንችልም ስለዚህ ይህ አስደሳች ቁጥር አይደለም። ቁጥሩ ወደ አንድ ከተቀነሰ ከዚያ የተሰጠው ቁጥር ደስተኛ ቁጥር ነው።

ኮድ

ለደስታ ቁጥር 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. ስለዚህ ፣ የጊዜ ውስብስብነቱ በቁጥር ውስጥ ባሉ አሃዞች ቁጥር ላይ የተመሠረተ ነው። እና በሎጋሪዝም ምክንያት እየቀነሰ ይሄዳል። ስለዚህ የጊዜ ውስብስብነት O (log N) ነው።

የቦታ ውስብስብነት

ኦ (logN) ፣ እነዚህን መካከለኛ ቁጥሮች ለማስቀመጥ ቦታ ያስፈልጋል ፡፡ ከጊዜ ውስብስብነት ጋር ተመሳሳይነት ያለው የቦታ ውስብስብነት እንዲሁ ሎጋሪዝም ነው።