K- നേക്കാൾ വലുതോ തുല്യമോ ആയ പ്രൈം ഫ്രീക്വൻസികളുള്ള അക്കങ്ങൾ


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു അക്കോലൈറ്റ് ആമസോൺ ഫാക്റ്റ്സെറ്റ് ഫോർകൈറ്റുകൾ ഗ്രേ ഓറഞ്ച് പോസ്റ്റ് സോം
അറേ ഹാഷ് പ്രൈം നമ്പർ

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

“K- നേക്കാൾ വലുതോ തുല്യമോ ആയ പ്രൈം ഫ്രീക്വൻസികളുള്ള നമ്പറുകൾ” എന്ന പ്രശ്‌നം, നിങ്ങൾക്ക് പൂർണ്ണസംഖ്യകളുടെ വലിപ്പവും n എന്ന സംഖ്യ മൂല്യവും നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു. അതിനുള്ളിലെ എല്ലാ അക്കങ്ങളും പ്രൈം നമ്പറുകളാണ്. അറേയിൽ‌ കുറഞ്ഞത് k തവണയെങ്കിലും ദൃശ്യമാകുന്ന അക്കങ്ങളും അറേയിലെ ഒരു പ്രധാന തവണയും കണ്ടെത്താൻ പ്രശ്ന പ്രസ്താവന ആവശ്യപ്പെടുന്നു.

ഉദാഹരണം

arr[] = {29, 11, 37, 53, 53, 53, 29, 53, 29, 53}, k = 2
29 and 53

വിശദീകരണം: 29 ഉം 53 ഉം യഥാക്രമം 3 തവണയും 5 തവണയും പ്രത്യക്ഷപ്പെടുന്നു, ഇത് കുറഞ്ഞത് k തവണയെങ്കിലും പ്രത്യക്ഷപ്പെടാനുള്ള അവസ്ഥയെ തൃപ്തിപ്പെടുത്തുന്നു.

K- നേക്കാൾ വലുതോ തുല്യമോ ആയ പ്രൈം ഫ്രീക്വൻസികളുള്ള സംഖ്യകൾ കണ്ടെത്താനുള്ള അൽഗോരിതം

1. Declare a map and store all the numbers of the array in the map with their frequencies.
2. Traverse the map.
    1. Check if the frequency of each element is at least k or greater than k.
    2. Find if that frequency is a prime number or not.
    3. If the frequency is a prime number then print that key else go for other numbers.

വിശദീകരണം

ഞങ്ങൾ പൂർണ്ണസംഖ്യകളുടെ ഒരു നിരയും k എന്ന മൂല്യവും നൽകി. നൽകിയിരിക്കുന്ന എല്ലാ അക്കങ്ങളും പ്രാഥമികമാണ്, ഈ സംഖ്യ കുറഞ്ഞത് k തവണയെങ്കിലും അറേയിലെ ഏതെങ്കിലും പ്രൈം നമ്പർ തവണയാണോ എന്ന് കണ്ടെത്താൻ ഞങ്ങൾ ആവശ്യപ്പെട്ടു, തുടർന്ന് ആ നമ്പർ പ്രിന്റുചെയ്യുക. ഇത് പരിഹരിക്കുന്നതിന്, ഞങ്ങൾ ഇത് ഉപയോഗിക്കും ഹാഷിംഗ് രീതി. ഞങ്ങൾ ഒരു ഉപയോഗിക്കും ഭൂപടം. ഞങ്ങളുടെ ചുമതല ഒരു സംഖ്യയുടെ രൂപം കണ്ടെത്തുക എന്നതാണ്, അതിനർത്ഥം ഓരോ മൂലകത്തിന്റെയും സംഭവങ്ങൾ കണ്ടെത്തേണ്ടതുണ്ട്, ഇത് പരിഹരിക്കുന്നതിന് ഞങ്ങൾ ഒരു മാപ്പ് ഉപയോഗിക്കാൻ പോകുന്നു.

ഞങ്ങൾ അറേയിലൂടെ സഞ്ചരിച്ച് ഓരോ ഘടകവും അതിന്റെ ആവൃത്തിയും മാപ്പിലേക്ക് എണ്ണുകയും സംഭരിക്കുകയും ചെയ്യും. നമ്പർ‌ മാപ്പിൽ‌ ഒരു പുതിയ എൻ‌ട്രിയാണെങ്കിൽ‌, മാപ്പിൽ‌ അതിനായി ഒരു സ്ഥലം ഉണ്ടാക്കി അതിന്റെ ആവൃത്തി 1 എന്ന് അടയാളപ്പെടുത്തുക. അതിന്റെ നമ്പർ. ഈ രീതിയിൽ, ഓരോ സംഖ്യയുടെയും എല്ലാ ആവൃത്തികളും നമുക്ക് കണക്കാക്കാം. ഓരോ സംഖ്യയുടെയും ആവൃത്തി, ആദ്യം k എണ്ണം എത്രതവണ ഉണ്ടെന്നും ഇപ്പോൾ ദൃശ്യമാകുന്ന എണ്ണം ഒരു പ്രൈം നമ്പറായിരിക്കുമോ എന്നും ഇപ്പോൾ പരിശോധിക്കേണ്ടതുണ്ട്.

അത്തരം സന്ദർഭങ്ങളിൽ, ഞങ്ങൾ ഓരോ കീയും ഒരു മാപ്പിലൂടെ സഞ്ചരിക്കുകയും അതിന്റെ ആവൃത്തി നേടുകയും ചെയ്യും. ആവൃത്തി ഒരു പ്രൈം നമ്പറാണോ അല്ലയോ എന്ന് പരിശോധിക്കുന്ന ഒരു ഫംഗ്ഷൻ ഞങ്ങൾ നടത്തി. പ്രൈം നമ്പറിനെ സംബന്ധിച്ചിടത്തോളം ഇത് 1 ആയിരിക്കരുത്, മാത്രമല്ല ഇത് തന്നേക്കാൾ മറ്റൊരു സംഖ്യ കൊണ്ട് ഹരിക്കരുത്. ഇത് ഏതെങ്കിലും സംഖ്യ കൊണ്ട് ഹരിക്കാമെങ്കിൽ തെറ്റായി മടങ്ങുക. ഇത് ഹരിക്കാവുന്നതാണെങ്കിൽ, ആ കീയുടെ അർത്ഥം ആ ആവൃത്തിയുടെ നമ്പർ അച്ചടിക്കുക, മറ്റൊരു നമ്പറിനായി മുന്നോട്ട് പോകുക.

 

K- നേക്കാൾ വലുതോ തുല്യമോ ആയ പ്രൈം ഫ്രീക്വൻസികളുള്ള അക്കങ്ങൾ

 

കോഡ്

K- നേക്കാൾ വലുതോ തുല്യമോ ആയ പ്രൈം ഫ്രീക്വൻസികളുള്ള സംഖ്യകൾ കണ്ടെത്തുന്നതിനുള്ള സി ++ കോഡ്

#include<iostream>
#include<unordered_map>

using namespace std;

bool checkIfPrime(int n)
{
    if (n <= 1)
        return false;

    for (int i = 2; i < n; i++)
        if (n % i == 0)
            return false;

    return true;
}
void numberWithPrimeFreq(int arr[], int k)
{
    unordered_map<int, int> MAP;

    for (int i = 0; i < 12; i++)
        MAP[arr[i]]++;

    for (auto x : MAP)
    {
        if (checkIfPrime(x.second) && x.second >= k)
            cout << x.first << endl;
    }
}
int main()
{
    int arr[] = { 29,11,37,53,53,53,29,53,29,53 };
    int k = 2;

    numberWithPrimeFreq(arr, k);
    return 0;
}
29
53

K- നേക്കാൾ വലുതോ തുല്യമോ ആയ പ്രൈം ഫ്രീക്വൻസികളുള്ള സംഖ്യകൾ കണ്ടെത്തുന്നതിനുള്ള ജാവ കോഡ്

import java.util.HashMap;
import java.util.Map;

public class  Frequencies_PrimeNumber
{
  public static void numberWithPrimeFreq(int[] arr, int k)
  {
    Map<Integer, Integer> MAP = new HashMap<>();

    for (int i = 0; i < arr.length; i++)
    {
      int val = arr[i];

      int freq;
      if (MAP.containsKey(val))
      {
        freq = MAP.get(val);
        freq++;
      }
      else
        freq = 1;
      MAP.put(val, freq);
    }
    for (Map.Entry<Integer, Integer> entry :MAP.entrySet())
    {
      int TEMP = entry.getValue();
      if (checkIfPrime(TEMP) && TEMP >= k)
        System.out.println(entry.getKey());
    }
  }
  private static boolean checkIfPrime(int n)
  {
    if ((n > 2 && n % 2 == 0) || n == 1)
      return false;

    for (int i = 2 ; i <n;	i ++)
    {
      if (n % i == 0)
        return false;
    }
    return true;
  }
  public static void main(String[] args)
  {
    int[] arr = { 29,11,37,53,53,53,29,53,29,53 };
    int k = 2;

    numberWithPrimeFreq(arr, k);
  }
}
53
29

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

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

ഇവിടെ, ആവൃത്തി k ഉള്ള n / k ഘടകങ്ങൾ ഉണ്ടെന്ന് പരിഗണിക്കുക, അതിനാൽ ഓരോ തവണയും പ്രാഥമികത പരിശോധിക്കും. പ്രാഥമിക പരിശോധനയ്ക്ക് O (n) സമയം മാത്രമേ എടുക്കൂ. ഇവിടെ n ആണ് ആവൃത്തി. അതിനാൽ ഏറ്റവും മോശം അവസ്ഥയിൽപ്പോലും, മുഴുവൻ അൽഗോരിതം രേഖീയ സമയത്ത് പ്രവർത്തിക്കാൻ കഴിയും. O (N) എവിടെ "N"  അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം.

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

ഇൻപുട്ട് സംഭരിക്കുന്നതിന് ആവശ്യമായ ഇടം കാരണം, O (N) എവിടെ "N"  അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം.