رقم سعيد


مستوى الصعوبة سهل
كثيرا ما يطلب في أدوبي أمازون أجهزة آبل 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 في كل مرة. إذا تم تقليل الرقم إلى 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

تحليل التعقيد

تعقيد الوقت

O (تسجيل N) ، يحتوي السجل N على القاعدة 10. لذا ، فإن تعقيد الوقت يعتمد على عدد الأرقام في الرقم. ويستمر في التناقص مع العامل اللوغاريتمي. وبالتالي فإن التعقيد الزمني هو O (log N).

تعقيد الفضاء

O (تسجيل الدخول) ، مطلوب مساحة لتخزين هذه الأرقام الوسيطة. على غرار تعقيد الوقت ، يكون تعقيد الفضاء أيضًا لوغاريتميًا.