मुबारक संख्या लीटकोड समाधान


कठिनाई तह सजिलो
बारम्बार सोधिन्छ एडोब अमेजन एप्पल
ह्याशिंग

समस्या वक्तव्य

समस्या जाँच गर्न को लागी एक नम्बर खुशी संख्या हो या छैन।

एक संख्या खुशी हुन भनिएको छ नम्बर यदि नम्बरलाई यसको अ of्कको वर्गमानको जोडले बदल्छ, र प्रक्रिया दोहोर्‍याउँदा संख्या १ बराबर हुन्छ। यदि यो १ हुँदैन र चक्रमा अन्तहीन रूपमा लूप हुन्छ जुन १ समावेश गर्दैन, यो खुशीको नम्बर छैन।

उदाहरणका

19
true

व्याख्या:

खुशी नम्बर

१ ^ २ + ^ = २ = .२
१ ^ २ + ^ = २ = .२
१ ^ २ + ^ = २ = .२
१ ^ २ + ० ^ २ + ० ^ २ = १ (खुशी नम्बर)

2
false

व्याख्या:

यो फेरि number नम्बरमा पुगेको छ, यहाँबाट यो सँधैको लागि सदाको लागि लुप हुन्छ र कहिले १ मा अन्त्य हुन सक्दैन। त्यसैले दिइएको संख्या खुसी संख्या होइन।

दृष्टिकोण

हामी केहि लूपमा पुनरावृत्ति गर्न सक्दछौं र अंकलाई १ को संख्या नभएसम्म यसको अंकको वर्गफलको साथ संख्या बदल्न सक्नेछौं, सर्तका साथ कि प्रत्येक नयाँ रूपान्तरित नम्बर नआएको हुनुपर्दछ अन्यथा हामी अनिश्चित लूपमा जान्छौं।
यसको लागि हामी पूर्णांकहरूको सेट लिन सक्दछौं, सुरूमा खाली र निम्न चरणहरू प्रदर्शन गर्न:

  1. यदि हालको संख्या पहिले नै सेट मा गलत फिर्ता उपस्थित छ (एक लुप भेट्टायो)।
  2. अन्यथा यदि यो १ फर्काउँछ भने ठीक हुन्छ।
  3. अन्यथा वर्तमान संख्यालाई सेटमा सम्मिलित गर्नुहोस् र हालको नम्बरलाई यसको अ of्कको वर्गमूलको साथ बदल्नुहोस्।
  4. उही प्रक्रिया दोहोर्याउनुहोस्।

कार्यान्वयन

C ++ हप्पी नम्बर Leetcode समाधानको लागि कार्यक्रम

#include <bits/stdc++.h>
using namespace std;

bool isHappy(int n) {
                 
    set<int> s;

    while(s.count(n)==0)
    {
        if(n==1) return true;
        s.insert(n);
        int temp=0;

        while(n)
        {
            temp+= (n%10)*(n%10);
            n/=10;
        }
        n=temp;
    }
    return false;
}

int main()
{ 
    int n=19;
    
    if(isHappy(n)) 
        cout<<"true"<<endl;
    else 
        cout<<"false"<<endl;
    
 return 0;
}
true

जाभा प्रोग्राम हेप्पी नम्बर लीटकोड समाधानको लागि

import java.util.*;
import java.lang.*;

class Happy
{  
     public static boolean isHappy(int n) 
     {
        
        Set<Integer> set = new HashSet<Integer>();
        int sum,digit;

        while (set.add(n)) 
        {
            sum = 0;
            while (n > 0) {
                digit = n%10;
                sum += digit*digit;
                n /= 10;
            }
            if (sum == 1)
                return true;
            else
                n = sum;

        }
        return false;
    }
    
    
    public static void main(String args[])
    {
       int n=19;
       System.out.println(isHappy(n));
    }
}
true

हैप्पी नम्बर लेटकोड समाधानको लागि जटिलता विश्लेषण

समय जटिलता

O (लगइन):  जहाँ n दिइएको संख्या हो। श्रृंखलामा संख्याको प्रत्येक अंकको वर्गफलको योग पत्ता लगाउन लागत लग (n) हो र संख्या लघुगणक कारकको साथ घट्दै जान्छ। यसैले जटिलता = O (लगइन) + O (लगलग्गन) + O (लगलग्गन) +…।
यहाँ O (log⁡n) प्रभुत्वको अंश हो। यसैले समग्र जटिलता O (लगइन) हो।

ठाउँ जटिलता 

O (लगइन):  सेटको अधिकतम आकार पनि समय जटिलता जस्ता दिइएको संख्याको साथ लोगारिथम हुनेछ।