Спецыяльны нумар


Узровень складанасці Лёгка
Часта пытаюцца ў 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 для спецыяльнага нумара

Грубая сіла

  • Мы праходзім па масіве
  • Мы правяраем элементы, якія дзеляць кожны элемент

Код 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 для спецыяльнага нумара

Выкарыстанне хэш-табліцы

Па-першае, давайце разбярэм падыход на невялікія прыемныя кавалачкі памерам укусу.

  • Спачатку адсартуйце ўсе элементы
  • Знайдзіце максімальны элемент, выкарыстоўваючы зменную
  • Патрэбны максімальны элемент?
  • З яго дапамогай можна знайсці дзельнікі да гэтага ліку
  • Пачынаем з нумара * 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

Заўвага: Апісаны вышэй падыход добра працуе толькі для невялікіх лічбаў

Аналіз складанасці для спецыяльнага нумара

Складанасць часу = O (n ^ 2)

  • Складанасць часу для падыходу складае да O (n ^ 2)
  • Сартаванне займае час O (n log n)
  • Праходзім па знешняй цыкле і выбіраем нумар з хэша
  • Ва ўнутраным цыкле мы шукаем дзельнікі і дадаем іх у набор, калі яны ёсць
  • У рэшце рэшт падвядзем складанасць часу да O (nlogn) + O (n ^ 2)
  • Як n ^ 2> n logn
  • Часавая складанасць становіцца O (n ^ 2)

Складанасць прасторы = O (n)

  • Мы выкарыстоўваем хэш і набор, каб адсочваць элементы.
  • У нас ёсць масіў / ArrayList / вектар памерам n.
  • Такім чынам, месца, якое займае захоўванне ўсіх элементаў, складае O (n).

Спасылкі