Optymalizacja kodu

Question

Witam,

stworzyłem działający kod który przyjmuje zbiór o mocy n, i liczbę k który ma znaleźć najmniejszą liczbę nienależącą do zbioru i podzielną przez k.  Jednak nie mieści się on w ramach czasowych zadania i chciałbym się dowiedzieć jak mogę go zoptymalizować. Oto wspomniany kod:

#include <bits/stdc++.h>
using namespace std;
vector <long long> vec;
int n;

bool isit(long long l)
{
    for (int i=0;i<n;i++)
    {
        if (l==vec[i])
        return 1;
    }
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    long long k,a,l=1;

    cin>>n>>k;

    for(int j=0;j<n;j++)
    {
        cin>>a;
        vec.push_back(a);
    }
    int i=1;
    while(true)
    {
        l=k*i;

        if (isit(l)==0)
        {
            cout<<l;
            return 0;
        }
        i++;
    }
}

 

Comments

znaleźć najmniejszą liczbę nienależącą do zbioru i podzielną przez k

Przy założeniu że dziedziną jest zbiór liczb całkowitych i dany zbiór o mocy n jest skończony, to taka liczba nie istnieje.

 

 

---

dowód: n +1 nie należy do zbioru i indykcyjnie da się to dowieść że istnieje taka liczba, ergo- zbiór jest skończony więc n+1 istnieje.
Autorowi albo brakuje faktu, że zbiór jest ograniczony od góry przez podaną wartość, albo że mowa "w dziedzinie jakiejs funkcji"

---

...o czym Wy mówicie? Dość jasnym jest że autorowi chodzi o

zbiór: 1 2 3 4 5 6 7 8
k: 5
najmniejsza liczba podzielna przez k ale nie będąca w zbiorze: 10

---

najmniejsza liczba podzielna przez k ale nie będąca w zbiorze: 10

Założyłeś że mamy tutaj do czynienia z liczbami naturalnymi. Autor nigdzie o tym nie wspomniał.

---

bo autor nie do precyzował tak mi się wydaje, samo zadanie brzmi niepełnie. w kwestii zbioru i zakresu np. dla liczby ograniczającej zbiór n

Answer 1

Hint: nie musisz dla każdej wielokrotności iterować się po całym zbiorze. Możesz zbiór albo posortować, albo... zamienić go na "prawdziwy" C++owy zbiór std::unordered_set i sprawdzać czy w nim jest.

Możesz też w trakcie wczytywania zbioru od razu przetwarzać tylko liczby podzielne przez k i zignorować resztę.