ഹാപ്പി നമ്പർ ലീറ്റ്കോഡ് പരിഹാരം


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു അഡോബി ആമസോൺ ആപ്പിൾ
ഹാഷിംഗ്

പ്രശ്നം പ്രസ്താവന

ഒരു സംഖ്യ സന്തുഷ്ട സംഖ്യയാണോ എന്ന് പരിശോധിക്കുക എന്നതാണ് പ്രശ്നം.

ഒരു സംഖ്യ സന്തുഷ്ടമാണെന്ന് പറയപ്പെടുന്നു അക്കം അക്കത്തെ അതിന്റെ അക്കങ്ങളുടെ സ്ക്വയറുകളുടെ ആകെത്തുക ഉപയോഗിച്ച് മാറ്റിസ്ഥാപിക്കുകയും പ്രക്രിയ ആവർത്തിക്കുകയും ചെയ്യുന്നത് സംഖ്യയെ 1 ന് തുല്യമാക്കുകയും ചെയ്യുന്നുവെങ്കിൽ, അത് 1 ആയിത്തീരുകയും 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 (ഹാപ്പി നമ്പർ)

2
false

വിശദീകരണം:

ഇത് വീണ്ടും നാലാം നമ്പറിലെത്തുമ്പോൾ, ഇവിടെ നിന്ന് അത് ശൃംഖലയിൽ എന്നെന്നേക്കുമായി ലൂപ്പുചെയ്യും, ഒരിക്കലും 4 ൽ അവസാനിക്കാൻ കഴിയില്ല. അതിനാൽ നൽകിയ നമ്പർ ഒരു സന്തോഷകരമായ സംഖ്യയല്ല.

സമീപനം

കുറച്ച് സമയ ലൂപ്പിൽ നമുക്ക് ആവർത്തനം ചെയ്യാനും സംഖ്യ 1 ആകുന്നതുവരെ അതിന്റെ അക്കങ്ങളുടെ ചതുരത്തിന്റെ ആകെത്തുക ഉപയോഗിച്ച് മാറ്റിസ്ഥാപിക്കാനും കഴിയും, ഓരോ പുതിയ പരിവർത്തനം ചെയ്ത സംഖ്യയും മുമ്പ് സംഭവിച്ചിരിക്കരുത് എന്ന നിബന്ധനയോടെ, അല്ലെങ്കിൽ ഞങ്ങൾ അനിശ്ചിതകാല ലൂപ്പിലേക്ക് പോകും.
ഇതിനായി നമുക്ക് ഒരു കൂട്ടം സംഖ്യകൾ എടുക്കാം, തുടക്കത്തിൽ ശൂന്യവും ഇനിപ്പറയുന്ന ഘട്ടങ്ങൾ നടപ്പിലാക്കുന്നതും:

  1. നിലവിലെ നമ്പർ ഇതിനകം തന്നെ സെറ്റ് റിട്ടേൺ തെറ്റാണെങ്കിൽ (ഒരു ലൂപ്പ് കണ്ടെത്തി).
  2. അല്ലെങ്കിൽ അത് 1 എന്നതിന് തുല്യമാണെങ്കിൽ ശരിയാണ്.
  3. അല്ലെങ്കിൽ നിലവിലെ നമ്പർ സെറ്റിലേക്ക് തിരുകുക, നിലവിലെ സംഖ്യയെ അതിന്റെ അക്കങ്ങളുടെ ചതുരത്തിന്റെ ആകെത്തുക ഉപയോഗിച്ച് മാറ്റിസ്ഥാപിക്കുക.
  4. സമാന പ്രക്രിയ ആവർത്തിക്കുക.

നടപ്പിലാക്കൽ

ഹാപ്പി നമ്പർ ലീറ്റ്കോഡ് പരിഹാരത്തിനായുള്ള സി ++ പ്രോഗ്രാം

#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

ഹാപ്പി നമ്പർ ലീറ്റ്കോഡ് പരിഹാരത്തിനായുള്ള സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

ഓ (ലോഗ്):  ഇവിടെ n എന്നത് നൽകിയിരിക്കുന്ന സംഖ്യയാണ്. ശൃംഖലയിലെ ഒരു അക്കത്തിന്റെ ഓരോ അക്കത്തിന്റെയും ചതുരത്തിന്റെ ആകെത്തുക കണ്ടെത്തുന്നതിനുള്ള ചെലവ് ലോഗ് (n) ആണ്, കൂടാതെ ലോഗരിഥമിക് ഘടകത്തിനൊപ്പം എണ്ണം കുറയുന്നു. അതിനാൽ സങ്കീർണ്ണത = O (logn) + O (loglogn) + O (logloglogn) +….
ഇവിടെ O (log⁡n) ആണ് പ്രധാന ഭാഗം. അതിനാൽ മൊത്തത്തിലുള്ള സങ്കീർണ്ണത O (ലോഗ്) ആണ്.

ബഹിരാകാശ സങ്കീർണ്ണത 

ഓ (ലോഗ്):  സമയ സങ്കീർണ്ണത പോലുള്ള തന്നിരിക്കുന്ന സംഖ്യയുള്ള സെറ്റിന്റെ പരമാവധി വലുപ്പവും ലോഗരിഥമിക് ആയിരിക്കും.