Специјален број


Ниво на тешкотија Лесно
Често прашувано во Jio 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 за посебен број

Brute Force

  • Ние поминуваме низ низата
  • Ние ги проверуваме елементите што го делат секој елемент

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; 
}

Анализа на сложеност

Временска комплексност = О (n ^ 2)

Како?

  • Горенаведениот пристап користи две јамки
  • Прво, надворешен да го надмине делителот
  • Второ. внатрешна да се надмине дивидендата
  • Ова ја носи сложеноста на времето до O (n ^ 2)

Вселенска комплексност = О (1)

Како?

Користиме само варијабла, затоа не ни треба многу простор

Пристап 2 за посебен број

Користење на хаш-табела

Прво, да го расипеме пристап на мали вкусни парчиња со големина на залак.

  • Прво сортирајте ги сите елементи
  • Пронајдете го максималниот елемент користејќи променлива
  • Потребен е елементот максимум?
  • Да го користите за да ги пронајдете достапните делители до тој број
  • Почнуваме од број * 2
  • Ние го додаваме бројот во себе за да ги добиеме множителите
  • Секој пат кога ќе добиеме повеќекратно, го чуваме во сет
  • Ние ги зачувуваме броевите во множества за да се осигураме дека ниту еден број што го добиваме не е дупликат
  • Ако има делител, тогаш бројот е посебен
  • Така се додава специјалниот број

Второ, дозволете ми да добијам мала слика за да го проверам целиот процес. Ова ќе осигури дека секој што не може да се справи со проблемот го разбира целосно.

Специјален број
Објаснет посебен број

Црвените места тука сугерираат дека броевите се веќе додадени на картата.

Java код

// "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

Белешка: Горенаведениот пристап работи добро само за мали броеви

Анализа на сложеност за посебен број

Временска комплексност = О (n ^ 2)

  • Временската комплексност за пристапот се сумира на О (n ^ 2)
  • Сортирањето трае O (n log n) време
  • Преминуваме преку надворешната јамка и одбираме број од хашот
  • Во внатрешната јамка, ги бараме делителите и ги додаваме во множеството ако се присутни
  • На крај, сумирање на временската сложеност до O (nlogn) + O (n ^ 2)
  • Како n ^ 2> n логн
  • Временската сложеност станува O (n ^ 2)

Вселенска комплексност = О (н)

  • Ние користиме хаш и сет за да ги следиме елементите.
  • Имаме низа / ArrayList / вектор со големина n.
  • Така, просторот зафатен во зачувување на сите елементи се сумира до О (n).

Референци