പ്രത്യേക നമ്പർ


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ജിയോ MAQ o9 പരിഹാരങ്ങൾ ടിസിഎസ്
നമ്പർ-അക്കങ്ങൾ സ്കൂൾ പ്രോഗ്രാമിംഗ്

ഒരു സംഖ്യയുടെ പ്രത്യേകത എന്താണ്?

നമുക്ക് അത് കണ്ടെത്താം.

ഞങ്ങളുടെ പക്കൽ N നമ്പറുകളുടെ ഒരു നിരയുണ്ട്. ഒരു സംഖ്യയെ ഒന്നോ അതിലധികമോ സംഖ്യകളാൽ വിഭജിച്ചാൽ ഒരു സംഖ്യ പ്രത്യേകമായിരിക്കും.

മറ്റെന്തെങ്കിലും കാര്യത്തിലേക്ക് കടക്കുന്നതിന് മുമ്പ് ആദ്യം ഇത് കുറച്ച് ഉദാഹരണങ്ങൾ ഉപയോഗിച്ച് മായ്‌ക്കാം

1,2,3 നിര

പ്രത്യേക നമ്പറുകൾ 2, 3

എന്തുകൊണ്ട്?

2 നെ 1 ഉം 3 ഉം കൊണ്ട് ഹരിക്കാം

1,2,5,9 ശ്രേണി

പ്രത്യേക നമ്പറുകൾ 2,5 ഉം 9 ഉം ആയിരിക്കും

എന്തുകൊണ്ട്?

ഈ സംഖ്യകളെ 1 കൊണ്ട് ഹരിക്കാം

2,3,4,6,8,9 ശ്രേണി

പ്രത്യേക നമ്പറുകൾ 4.6.8.9 ആയിരിക്കും

രണ്ടാമതായി, ഈ പ്രശ്നത്തെ എങ്ങനെ സമീപിക്കാം എന്ന് നോക്കാം

പ്രത്യേക നമ്പറിനായി 1 നെ സമീപിക്കുക

ബ്രൂട്ട് ഫോഴ്സ്

  • ഞങ്ങൾ നിരയിലൂടെ സഞ്ചരിക്കുന്നു
  • ഓരോ ഘടകത്തെയും വിഭജിക്കുന്ന ഘടകങ്ങൾ ഞങ്ങൾ പരിശോധിക്കുന്നു

പ്രത്യേക നമ്പറുകൾക്കുള്ള ജാവ കോഡ്

// "static void main" must be defined in a public class.
public class Main 
{
    public static void diCheck(List<Integer> arr, int n) 
    { 
        Set<Integer> store = new HashSet<Integer>(); 
        for(int i=0;i<arr.size();i++)
        {
            for(int j=i+1;j<arr.size();j++)
            {
                if(arr.get(j)%arr.get(i)==0)
                    store.add(arr.get(j));
            }
        }
        for(Integer a:store)
        {
            System.out.print(a+" ");
        }
    } 
    public static void main(String[] args) 
    {
        List<Integer> arr = Arrays.asList(1, 2, 3, 8, 6, 9, 5); 
        int n = arr.size(); 
        diCheck(arr, n); 
    }
}

പ്രത്യേക നമ്പറുകൾക്കുള്ള സി ++ കോഡ്

void diCheck(int arr[], int n) 
{ 
    unordered_set<int> store; 
    int maxs = -1; 
    for (int i = 0; i < n; i++) 
    { 
        for(int j=i+1;j<n;j++)
        {
            if(arr[j]%arr[i]==0)
                store.insert(arr[j]);
        }
    } 
    for (auto x : store) 
        cout << x << " "; 
} 
int main() 
{ 
    int arr[] = { 1, 2, 3, 5, 8, 6, 9, 10 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
  
    diCheck(arr, n); 
  
    return 0; 
}

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത = O (n ^ 2)

എങ്ങനെ?

  • മുകളിലുള്ള സമീപനം രണ്ട് ലൂപ്പുകൾ ഉപയോഗിക്കുന്നു
  • ഒന്നാമതായി, ഹരണത്തിന് മുകളിലൂടെ പോകാൻ പുറം
  • രണ്ടാമതായി. ലാഭവിഹിതം മറികടക്കാൻ ആന്തരികം
  • ഇത് സമയ സങ്കീർണ്ണത O (n ^ 2) ലേക്ക് കൊണ്ടുവരുന്നു

ബഹിരാകാശ സങ്കീർണ്ണത = O (1)

എങ്ങനെ?

ഞങ്ങൾ ഒരു വേരിയബിൾ മാത്രമേ ഉപയോഗിക്കുന്നുള്ളൂ അതിനാൽ ഞങ്ങൾക്ക് കൂടുതൽ സ്ഥലം ആവശ്യമില്ല

പ്രത്യേക നമ്പറിനായി 2 നെ സമീപിക്കുക

ഒരു ഹാഷ് പട്ടിക ഉപയോഗിക്കുന്നു

ഒന്നാമതായി, നമുക്ക് അത് തകർക്കാം സമീപനം ചെറിയ വലിപ്പത്തിലുള്ള രുചികരമായ കഷണങ്ങളായി.

  • ആദ്യം എല്ലാ ഘടകങ്ങളും അടുക്കുക
  • ഒരു വേരിയബിൾ ഉപയോഗിച്ച് പരമാവധി ഘടകം കണ്ടെത്തുക
  • പരമാവധി ഘടകത്തിന്റെ ആവശ്യമുണ്ടോ?
  • ആ നമ്പർ വരെ ലഭ്യമായ ഹരണങ്ങൾ കണ്ടെത്താൻ ഇത് ഉപയോഗിക്കുന്നതിന്
  • ഞങ്ങൾ നമ്പർ * 2 ൽ നിന്ന് ആരംഭിക്കുന്നു
  • ഗുണിതങ്ങൾ ലഭിക്കുന്നതിന് ഞങ്ങൾ അതിൽ തന്നെ നമ്പർ ചേർക്കുന്നു
  • ഓരോ തവണയും ഒന്നിലധികം ലഭിക്കുമ്പോൾ ഞങ്ങൾ അത് ഒരു സെറ്റിലേക്ക് സൂക്ഷിക്കുന്നു
  • ഞങ്ങൾ‌ നേടുന്ന അക്കങ്ങളൊന്നും തനിപ്പകർ‌പ്പല്ലെന്ന് ഉറപ്പാക്കുന്നതിന് ഞങ്ങൾ‌ അക്കങ്ങളെ സെറ്റുകളായി സംഭരിക്കുന്നു
  • ഒരു ഹരിക്കൽ ഉണ്ടെങ്കിൽ നമ്പർ പ്രത്യേകമാണ്
  • പ്രത്യേക നമ്പർ ഇങ്ങനെ ചേർത്തു

രണ്ടാമതായി, മുഴുവൻ പ്രക്രിയയിലും പ്രവർത്തിക്കാൻ ഒരു ചെറിയ ചിത്രം നേടട്ടെ. പ്രശ്‌നത്തെക്കുറിച്ച് ഒരു പിടി നേടാൻ കഴിയാത്ത എല്ലാവരും ഇത് പൂർണ്ണമായി മനസ്സിലാക്കുന്നുവെന്ന് ഇത് ഉറപ്പാക്കും.

പ്രത്യേക നമ്പർ
പ്രത്യേക നമ്പർ വിശദീകരിച്ചു

ഇവിടെയുള്ള ചുവന്ന സ്ഥലങ്ങൾ ഇതിനകം തന്നെ മാപ്പിൽ നമ്പറുകൾ ചേർത്തിട്ടുണ്ടെന്ന് സൂചിപ്പിക്കുന്നു.

ജാവ കോഡ്

// "static void main" must be defined in a public class.
public class Main 
{
    public static void diCheck(List<Integer> arr, int n) 
    { 
        List<Integer> store = new ArrayList<Integer>(); 
        int max = Integer.MIN_VALUE; 
        for (int i = 0; i < n; i++) 
        { 
            store.add(arr.get(i)); 
            max = Math.max(max,arr.get(i)); 
        }
        LinkedHashSet<Integer>ans=new LinkedHashSet<Integer>();
        for(int i=0;i<n;i++)
        {
            if(arr.get(i)!=0)
            {
                for(int j=arr.get(i)*2;j<max;j++)
                {
                    if(store.contains(j))
                        ans.add(j);
                }
            }
        }
        List<Integer>ret=new ArrayList<Integer>(ans);
        for(int i=0;i<ret.size();i++)
            System.out.print(ret.get(i)+" ");
    } 
    public static void main(String[] args) 
    {
        List<Integer> arr = Arrays.asList(1, 2, 3, 8, 6, 9, 5); 
        int n = arr.size(); 
        diCheck(arr, n); 
    }
}

സി ++ കോഡ്

void diCheck(int arr[], int n) 
{ 
    unordered_set<int> store; 
    int maxs = -1; 
    for (int i = 0; i < n; i++) 
    { 
        store.insert(arr[i]); 
        //Finding the max element 
        maxs= max(maxs, arr[i]); 
    } 
  
    // Traversing the array elements and storing the multiples
    unordered_set<int> res; 
    for (int i = 0; i < n; i++) 
    { 
        if (arr[i] != 0) 
        { 
            for (int j = arr[i] * 2; j <= maxs; j++)
            { 
                if (store.find(j) != store.end()) 
                    res.insert(j); 
            } 
        } 
    } 
    unordered_map<int, int> map; 
    for(int i = 0; i < n; i++) 
        map[arr[i]]=map[arr[i]]+1; 
  
    unordered_map<int, int>::iterator it; 
    vector<int> ans; 
    for (it = map.begin(); it != map.end(); it++) 
    { 
        if (it->second >= 2) 
        { 
            if (res.find(it->first) == res.end()) 
            { 
                int val = it->second; 
                while (val--) 
                    ans.push_back(it->first); 
            } 
        } 
  
        // If frequency is greater than 1 and is divisible by any other number 
        if (res.find(it->first) != res.end()) 
        { 
            int val = it->second; 
            while (val--) 
                ans.push_back(it->first); 
        } 
    }
    //Printing special numbers
    for (auto x : ans) 
        cout << x << " "; 
} 
int main() 
{ 
    int arr[] = { 1, 2, 3, 5, 8, 6, 9, 10 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
  
    diCheck(arr, n); 
  
    return 0; 
}
1, 2, 3, 5, 8, 6, 9, 10
2,3,5,8,9,10

കുറിപ്പ്: മുകളിലുള്ള സമീപനം ചെറിയ സംഖ്യകൾക്ക് മാത്രം നന്നായി പ്രവർത്തിക്കുന്നു

പ്രത്യേക നമ്പറിനായി സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത = O (n ^ 2)

  • സമീപനത്തിനുള്ള സമയ സങ്കീർണ്ണത O (n ^ 2) വരെയാണ്
  • തരംതിരിക്കലിന് O (n log n) സമയമെടുക്കും
  • ഞങ്ങൾ ബാഹ്യ ലൂപ്പിന് മുകളിലൂടെ പോയി ഹാഷിൽ നിന്ന് ഒരു നമ്പർ തിരഞ്ഞെടുക്കുക
  • ആന്തരിക ലൂപ്പിൽ, ഞങ്ങൾ ഹരണങ്ങൾ തിരയുകയും അവ ഉണ്ടെങ്കിൽ അവ സെറ്റിലേക്ക് ചേർക്കുകയും ചെയ്യുന്നു
  • ക്രമേണ സമയ സങ്കീർണ്ണതയെ O (nlogn) + O (n ^ 2) ലേക്ക് സംഗ്രഹിക്കുന്നു
  • N ^ 2> n ലോഗ് ആയി
  • സമയ സങ്കീർണ്ണത O (n ^ 2) ആയി മാറുന്നു

ബഹിരാകാശ സങ്കീർണ്ണത = O (n)

  • ഘടകങ്ങളുടെ ട്രാക്ക് സൂക്ഷിക്കാൻ ഞങ്ങൾ ഒരു ഹാഷും ഒരു സെറ്റും ഉപയോഗിക്കുന്നു.
  • ഞങ്ങൾക്ക് നൽകിയിരിക്കുന്ന n ന്റെ ഒരു അറേ / അറേലിസ്റ്റ് / വെക്റ്റർ ഉണ്ട്.
  • അങ്ങനെ എല്ലാ ഘടകങ്ങളും സംഭരിക്കുന്നതിന് എടുത്ത ഇടം O (n) വരെ ആകും.

അവലംബം