E. Cyclic Components
resource
হিন্টঃ প্রতিটি কম্পোনেন্ট এ চেক করবো তাদের প্রত্যেকটি নোডের ডিগ্রি দুই কিনা, যদি দুই হয় তাইলে সেটা একটা সিঙ্গেল সাইকেল কম্পোনেন্ট।
Showing posts with label GeeksForGeeks. Show all posts
Showing posts with label GeeksForGeeks. Show all posts
Heap Sort
Heap Sort
Time Complexity: Time complexity of heapify is O(nLogn). Time complexity of createAndBuildHeap() is O(n) and overall time complexity of Heap Sort is O(nLogn).
hackerearth
GeeksForGeeks
visualization
maximum XOR
Maximum XOR value of a pair from a range
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 | #include <bits/stdc++.h> using namespace std; #define INF 1<<30 #define MAX 10005 #define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); typedef long long ll; int MaxXORInRange(int l, int r) { int LXR = l ^ r; // xor limits int msbPos = 0; while(LXR){ msbPos++; LXR >>= 1; } int maxXOR = 0; int two = 1; while(msbPos--){ maxXOR += two; two <<= 1; } return maxXOR; } int main() { FASTIO ///* //double start_time = clock(); #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); freopen("error.txt", "w", stderr); #endif //*/ int L,R; cin >> R >> R; cout << MaxXORInRange(L,R)<<endl; //double end_time = clock(); //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000); return 0; } |
Find the maximum subarray XOR in a given array
O(N^2) solution
Anther O(N) solution using Trie Tree: Gist_Link
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 | #include <bits/stdc++.h> using namespace std; #define INF 1<<30 #define MAX 10005 #define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); typedef long long ll; #define INT_SIZE 32 struct TrieNode { int value; TrieNode *ar[2]; }; TrieNode *newNode() { TrieNode *temp = new TrieNode; temp->value = 0; temp->ar[0] = temp->ar[1] = NULL; return temp; } void insert(TrieNode *root, int pre_xor) { TrieNode *temp = root; for(int i = INT_SIZE - 1; i >= 0; i--){ bool val = pre_xor & (1 << i); if(temp->ar[val] == NULL) temp->ar[val] = newNode(); temp = temp->ar[val]; } temp->value = pre_xor; } int query(TrieNode *root, int pre_xor) { TrieNode *temp = root; for(int i = INT_SIZE - 1; i >= 0; i--){ bool val = pre_xor & (1 << i); if(temp->ar[1-val] != NULL) temp = temp->ar[1-val]; else if(temp->ar[val] != NULL) temp = temp->ar[val]; } return pre_xor ^ (temp->value); } int maxSubarrayXOR(int ar[], int n) { TrieNode *root = newNode(); insert(root, 0); int res = INT_MIN, pre_xor = 0; for(int i = 0; i < n; i++){ pre_xor = pre_xor ^ ar[i]; insert(root, pre_xor); res = max(res, query(root, pre_xor)); } return res; } int main() { FASTIO ///* //double start_time = clock(); #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); freopen("error.txt", "w", stderr); #endif //*/ int n; cin >> n; int a[n+2]; for(int i = 0; i < n; i++){ cin >> a[i]; } cout << maxSubarrayXOR(a,n)<< endl; //double end_time = clock(); //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000); return 0; } |