Data_Structures_and_Algorithms/unorderedset.cpp at master · sukritidawar/Data_Structures_and_Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<bits/stdc++.h>
#include<unordered_set>
using namespace  std;

void print_distinct_elements(int arr[], int n){ //O(n) time
    unordered_set<int> s;
    for(int i = 0; i < n; i++){
        s.insert(arr[i]);
    }
    for(auto it = s.begin(); it != s.end(); it++){
        cout << *it << " ";
    }
    // for(int i = 0; i < n; i++){      //for printing distinct elements in the same order as they were in the array //O(n) time
    //     if(s.find(arr[i]) == s.end()){
    //         cout << arr[i] << " ";
    //         s.insert(arr[i]);
    //     }
    // }
}

void print_repeating_elements(vector<int> arr){ //O(n) time and O(n) aux space
    unordered_set<int> s;
    for(int i = 0; i < arr.size(); i++){
        if(s.find(arr[i]) == s.end()){
            s.insert(arr[i]);
        }else{
            cout << arr[i] << " ";
        }
    }
}

bool findPairwithgivenSum(int arr[], int n, int sum){ //O(n) time and O(n) aux space
    unordered_set<int> s;
    for(int i = 0; i < n; i++){
        if(s.find(sum - arr[i]) != s.end()){
            s.insert(arr[i]);
        }else{
            return true;
        }
    }
    return false;
}

void printIntersectionelements(int arr1[], int n1, int arr2[], int n2){ //O(n1 + n2) time , O(n) aux space
    unordered_set<int> s;
    for(int i = 0; i < n2; i++){
        s.insert(arr2[i]);
    }
    for(int i = 0; i < n1; i++){
        if(s.find(arr1[i]) != s.end()){
            cout << arr1[i] << " ";
        }
    }
}

int maxTypesofElements(int arr[], int n, int k){ //O(n) time and O(n) aux space
    unordered_set<int> s;
    int d = 0;
    for(int i = 0; i < n; i++){
        if(s.find(arr[i]) == s.end()){
            s.insert(arr[i]);
            d++;
        }
    }
    int nbyk = n / k;
    if(d >= nbyk){return nbyk;}
    else{return d;}
}

int getLongestSubsequence(int arr[], int n){
    int res = 0;
    unordered_set<int> s;
    for(int i = 0; i < n; i++){
        s.insert(arr[i]);
    }
    for(int i = 0; i < n; i++){
        if(s.find(arr[i] - 1) == s.end()){
            int curr = 1;
            while(s.find(arr[i] + curr) != s.end()){
                curr++;
            }
            res = max(res, curr);
        }
    }
    return res;
}

bool subarrwithZeroSum(int arr[], int n){ //O(n) time and O(n) aux space
    unordered_set<int> s;
    int pre_sum = 0;
    for(int i = 0; i < n; i++){
        pre_sum += arr[i];
        if(s.find(pre_sum) != s.end()){
            return true;
        }
        if(pre_sum == 0){
            return true;
        }
        s.insert(pre_sum);
    }
    return false;
}

int main(int argc, char** argv){
    int arr[] = {1, 5, 7, -1};
    int n = sizeof(arr) / sizeof(arr[0]);
    // print_distinct_elements(arr, n);
    // vector<int> arr(5, 0);
    // for(int i = 0; i < arr.size(); i++){
    //     cin >> arr[i];
    // }
    // print_repeating_elements(arr);
    cout << findPairwithgivenSum(arr, n, 2);
    int arr2[] = {10, 10, 5, 2};
    // printIntersectionelements(arr, n, arr2, 4);
    // cout << maxTypesofElements(arr, n, 2);
    // cout << getLongestSubsequence(arr, n);
    return 0;
}