This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
vector < int >Solution::repeatedNumber (const vector < int >&arr) { | |
/* Will hold xor of all elements and numbers from 1 to n */ | |
int xor1; | |
/* Will have only single set bit of xor1 */ | |
int set_bit_no; | |
int i; | |
int x = 0; // missing | |
int y = 0; // repeated |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
#include <bits/stdc++.h> | |
pair<int,int> missingAndRepeating(vector<int> &arr, int n) | |
{ | |
int mp[n+1] = {0}; | |
for(int i=0; i<n; i++) | |
mp[arr[i]]++; | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public: | |
int findDuplicate(vector<int>& nums) { | |
int tort = nums[0], hare = nums[0]; | |
do{ | |
tort = nums[tort]; | |
hare = nums[nums[hare]]; | |
}while(tort != hare); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public: | |
// Find the position of the Most Significant Bit in num | |
int calcMaxBit(int num) { | |
int bits = 0; | |
while (num > 0) { | |
num /= 2; | |
bits++; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public: | |
int findDuplicate(vector<int>& nums) { | |
// Lambda function to count how many numbers are less than or equal to 'cur' | |
auto small_or_equal = [&](int cur) { | |
int count = 0; | |
for (auto &num: nums) { | |
if (num <= cur) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public: | |
int findDuplicate(vector<int>& nums) { | |
for(int i=0; i<nums.size(); i++){ | |
int absNum = abs(nums[i]); | |
if(nums[absNum] < 0){ | |
// Number is duplicate | |
return absNum; | |
} | |
nums[absNum] = -nums[absNum]; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public: | |
int findDuplicate(vector<int>& nums) { | |
unordered_set<int> seen; | |
for (auto &num : nums) { | |
if (seen.count(num)) | |
return num; | |
seen.insert(num); | |
} | |
return -1; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public: | |
int findDuplicate(vector<int>& nums) { | |
sort(nums.begin(), nums.end()); | |
for (int i = 1; i < nums.size(); i++) { | |
if (nums[i] == nums[i - 1]) | |
return nums[i]; | |
} | |
return -1; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
void recurse(int index, int N, vector<int> &num, vector<int> &sum, int sumSoFar){ | |
if(index == N){ | |
sum.push_back(sumSoFar); | |
return; | |
} | |
recurse(index+1, N, num, sum, sumSoFar+num[index]); | |
recurse(index+1, N, num, sum, sumSoFar); | |
return; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
using namespace std; | |
class Solution { | |
void dfs(int node, vector<int> &vis, vector<int> adj[], vector<int> &storeDfs) { | |
storeDfs.push_back(node); | |
vis[node] = 1; | |
for(auto it : adj[node]) { | |
if(!vis[it]) { | |
dfs(it, vis, adj, storeDfs); | |
} |
NewerOlder