מספר שמח


רמת קושי קַל
נשאל לעתים קרובות Adobe אמזון בעברית תפוח עץ JP מורגן
בליל חבטות מתמטיקה

הצהרת בעיה

מהו מספר שמח?

מספר הוא מספר שמח אם נוכל לצמצם מספר נתון ל- 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 בכל פעם. אם המספר מצטמצם לחזרה אחת אמיתי אחרת תחזיר שקר.

דוגמה

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 למספר Happy

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 יש בסיס 10. אז מורכבות הזמן תלויה במספר הספרות במספר. וזה ממשיך לרדת עם הגורם הלוגריתמי. לפיכך מורכבות הזמן היא O (יומן N).

מורכבות בחלל

O (logN), נדרש מקום לאחסון מספרי ביניים אלה. בדומה למורכבות הזמן גם מורכבות החלל היא לוגריתמית.