Атайын номер


Кыйынчылык деңгээли жеңил
Көп суралган Джио MAQ o9 чечимдери TCS
Сандар-сандар Мектеп программасы

Номердин өзгөчөлүгү эмнеде?

Кел, карап көрөлү.

Бизде 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-ыкма

Кара күч

  • Биз массив аркылуу өтөбүз
  • Ар бир элементти бөлгөн элементтерди текшеребиз

Атайын Номерлер үчүн Java коду

// "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); 
    }
}

C ++ коду атайын номерлер үчүн

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-ыкма

Хэш таблицасын колдонуу

Биринчиден, келгиле жакындоо чакан чаккан даамдуу бөлүктөргө.

  • Биринчиден, бардык элементтерди иреттөө
  • Өзгөрмөчтү колдонуп, max элементин тап
  • Max элементи керекпи?
  • Аны ушул санга чейин жеткиликтүү бөлүштүргүчтөрдү табуу үчүн колдонуу
  • Биз num * 2ден баштайбыз
  • Көпчүлүктөрдү алуу үчүн санды өзүнө кошобуз
  • Бир нече эселенген сайын, аны топтомго сактайбыз
  • Биз алган сандардын бири дагы кайталанбашы үчүн, сандарды топтомдордо сактайбыз
  • Эгерде бөлүүчү бар болсо, анда анын саны өзгөчө болот
  • Ошентип атайын номер кошулат

Экинчиден, мага бүткүл процессти чагылдырып берүү үчүн кичинекей сүрөт алып берейин. Бул көйгөйдү түшүнө албаган ар бир адам аны толук түшүнүүсүн камсыз кылат.

Атайын номер
Атайын номер түшүндүрүлдү

Бул жердеги кызыл жерлер сандар картага мурунтан эле кошулган деп божомолдойт.

Java Code

// "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); 
    }
}

C ++ коду

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 logn катары
  • Убакыттын татаалдыгы O (n ^ 2) болуп калат

Космостун татаалдыгы = O (n)

  • Элементтерди көзөмөлдөө үчүн таштанды жана топтомду колдонобуз.
  • Бизде n көлөмүндөгү массив / ArrayList / вектор бар.
  • Ошентип, бардык элементтерди сактоодо орун O (n) түзөт.

шилтемелер