Посебан број


Ниво тешкоће Лако
Често питани у јио МАК о9 решења ТЦС
Бројеви-цифре Школско програмирање

Шта може бити толико посебно у вези са бројем?

Хајде да сазнамо.

Са собом имамо низ од Н бројева. Број може бити посебан ако је дељив са једним или више бројева, осим са самим бројем.

Прво да то рашчистимо са неколико примера пре него што пређемо на било шта друго

Низ од 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; 
}

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

Сложеност времена = О (н ^ 2)

Како?

  • Горњи приступ користи две петље
  • Прво, спољни за прелазак делитеља
  • Друго. унутрашња за прелазак на дивиденду
  • Ово временску сложеност доводи до О (н ^ 2)

Сложеност простора = О (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

Напомена: Горњи приступ добро функционише само за мале бројеве

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

Сложеност времена = О (н ^ 2)

  • Временска сложеност приступа износи О (н ^ 2)
  • За сортирање је потребно О (н лог н) време
  • Прелазимо преко спољне петље и бирамо број из хеша
  • У унутрашњој петљи тражимо делиоце и додајемо их у скуп ако су присутни
  • На крају сумирање временске сложености на О (нлогн) + О (н ^ 2)
  • Као н ^ 2> н логн
  • Временска сложеност постаје О (н ^ 2)

Сложеност простора = О (н)

  • За праћење елемената користимо хеш и сет.
  • Имамо обезбеђени низ / АрраиЛист / вектор величине н.
  • Тако се простор за складиштење свих елемената сумира до О (н).

Референце