Skip to content

Instantly share code, notes, and snippets.

View Ch-sriram's full-sized avatar
🎯
Achieving Greatness | Non-stop Hustling

Sriram Chandrabhatta Ch-sriram

🎯
Achieving Greatness | Non-stop Hustling
38 followers · 30 following
View GitHub Profile
@Ch-sriram
Ch-sriram / connected-components-dfs.cpp
Created October 31, 2020 20:02
Number of Connected Components [TC: O(V+E); SC: O(V)]
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
void DFSRec(vector<int> *G, int src, vector<bool> &visited) {
visited[src] = true;
for(int u: G[src])
if(!visited[u])
DFSRec(G, u, visited);
@Ch-sriram
Ch-sriram / bfs-graph.cpp
Created October 31, 2020 17:48
BFS of Graph [TC: O(V+E); SC: O(V)]
// Problem Link: https://practice.geeksforgeeks.org/problems/bfs-traversal-of-graph/1/
/* Function to do BFS of graph
* g[]: adj list of the graph
* N : number of vertices
*/
vector<int> bfs(vector<int> g[], int N) {
vector<int> vertices;
vector<bool> visited(N+1, false);
queue<int> Q;
@Ch-sriram
Ch-sriram / connected-components-bfs.cpp
Created October 31, 2020 17:22
Count Number of Connected Components [TC: O(V+E); SC: O(V+E)]
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
void addEdge(vector<int> *adj, int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
@Ch-sriram
Ch-sriram / print-adj-list.cpp
Created October 31, 2020 17:03
Print Adjacency List [TC: O(V+E); SC: O(1)]
// Problem Link: https://practice.geeksforgeeks.org/problems/print-adjacency-list-1587115620/1/
// The Graph structure is as folows
// Function to print graph
// adj: array of vectors to represent graph
// V: number of vertices
void printGraph(vector<int> adj[], int V) {
for(int u = 0; u < V; ++u) {
if((int)adj[u].size() == 0) cout << u;
@Ch-sriram
Ch-sriram / max-xor-subset.cpp
Last active October 31, 2020 04:35
Maximum XOR Subset [TC: O(32*(2N)); SC: O(1)]
// Problem Link: https://practice.geeksforgeeks.org/problems/maximum-subset-xor/1/
// Good Explanation: https://www.geeksforgeeks.org/find-maximum-subset-xor-given-set/
int maxXor(int arr[], int n) {
int maxEle = INT_MIN;
for(int i = 0; i < n; ++i)
maxEle = max(maxEle, arr[i]);
int MSB = 0;
for(int i = 31; i >= 0; --i)
@Ch-sriram
Ch-sriram / max-array-xor.cpp
Last active October 31, 2020 04:16
Maximum Array XOR [TC: O(32*(2N)); SC: O(1)]
// Problem Link: https://practice.geeksforgeeks.org/problems/maximum-subset-xor/1/
// Good Explanation: https://www.geeksforgeeks.org/find-maximum-subset-xor-given-set/
int maxSubarrayXOR(int arr[], int n) {
int maxEle = INT_MIN;
for(int i = 0; i < n; ++i)
maxEle = max(maxEle, arr[i]);
int MSB = 0;
for(int i = 31; i >= 0; --i)
@Ch-sriram
Ch-sriram / max-AND-value.cpp
Created October 29, 2020 22:39
Maximum AND Value [TC: O(32*N); SC: O(1)]
// Problem Link: https://practice.geeksforgeeks.org/problems/maximum-and-value2637/1
int checkBit(int pattern, int arr[], int n) {
int count = 0;
for(int i = 0; i < n; ++i)
if((pattern & arr[i]) == pattern)
++count;
return count;
}
// Function for finding maximum and value pair
@Ch-sriram
Ch-sriram / num-sparse-or-not.cpp
Created October 29, 2020 20:45
Number is Sparse or Not [TC: O(logN); SC: O(1)]
// Problem Link: https://practice.geeksforgeeks.org/problems/number-is-sparse-or-not-1587115620/1/
bool isSparse(int n) {
for(int i = 0; i < 32; ++i)
if(((n >> i) & 3) == 3)
return false;
return true;
}
@Ch-sriram
Ch-sriram / swap-odd-even-bits.cpp
Created October 29, 2020 20:20
Swap All Odd & Even Bits [TC: O(logN); SC: O(1)]
// Problem Link: https://practice.geeksforgeeks.org/problems/swap-all-odd-and-even-bits-1587115621/1/
unsigned int swapBits(unsigned int n) {
for(uint32_t i = 0; i < 32; i += 2) {
uint32_t requiredBits = ((n >> i) & 3) ^ 3;
if(requiredBits == 1 || requiredBits == 2)
n ^= (3 << i);
}
return n;
}
@Ch-sriram
Ch-sriram / bit-difference.cpp
Created October 29, 2020 19:51
Bit Difference [TC: O(logN); SC: O(1)]
// Problem Link: https://practice.geeksforgeeks.org/problems/bit-difference-1587115620/1/
int countSetBits(int n) {
int count = 0;
while(n) {
++count;
n &= (n-1);
}
return count;
}