ഹാപ്പി നമ്പർ


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

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

എന്താണ് സന്തോഷകരമായ നമ്പർ?

ഈ പ്രക്രിയയെത്തുടർന്ന് നൽകിയ ഒരു സംഖ്യയെ 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

ഹാപ്പി നമ്പർ

നമുക്ക് ഈ സംഖ്യയെ ഒന്നായി കുറയ്‌ക്കാൻ കഴിയും അതിനാൽ ഇത് സന്തോഷകരമായ ഒരു സംഖ്യയാണ്.

സമീപനം

ഈ പ്രശ്നം വളരെ ലളിതവും സെറ്റിന്റെ അടിസ്ഥാന ആശയം മാത്രം ഉപയോഗിക്കുന്നു.

എന്താണ് ഒരു സെറ്റ്?

അദ്വിതീയ ഘടകങ്ങൾ ഉള്ള ഒരു അനുബന്ധ കണ്ടെയ്‌നറാണ് സെറ്റ്.

ഈ പ്രശ്നം പരിഹരിക്കാൻ ഞങ്ങൾ ഒരു ഉപയോഗിക്കും ഗണം. സെറ്റിൽ, അക്കത്തിന്റെ അക്കങ്ങളുടെ ചതുരം ചേർത്തതിനുശേഷം ഞങ്ങൾ പുതുതായി രൂപംകൊണ്ട നമ്പർ ഉൾപ്പെടുത്തും. ഇപ്പോൾ ഘടകം ഇതിനകം സെറ്റിൽ ഉണ്ടെങ്കിൽ അതിനർത്ഥം അത് ഒരു ലൂപ്പ് ഉണ്ടാക്കുന്നുവെന്നും ഞങ്ങൾക്ക് നൽകിയ സംഖ്യയെ ഒന്നായി പരിവർത്തനം ചെയ്യാൻ കഴിയില്ലെന്നും അതിനാൽ ഇത് സന്തോഷകരമായ ഒരു സംഖ്യയല്ല. നമ്പർ ഒന്നായി കുറച്ചാൽ, നൽകിയ നമ്പർ ഒരു സന്തോഷകരമായ നമ്പറാണ്.

കോഡ്

ഹാപ്പി നമ്പറിനായുള്ള സി ++ കോഡ്

#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 (ലോഗ് N) ആണ്.

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

O (logN), ഈ ഇന്റർമീഡിയറ്റ് നമ്പറുകൾ സംഭരിക്കുന്നതിന് ഇടം ആവശ്യമാണ്. സമയ സങ്കീർണ്ണതയ്ക്ക് സമാനമായി ബഹിരാകാശ സങ്കീർണ്ണതയും ലോഗരിഥമിക് ആണ്.