y = x & (-x) or y = x & !(x-1) - Get the rightmost 1's bit
y = x & (x-1) - Unset rightmost 1's bit
Find the two non-repeating elements in an array of repeating elements
swap numbers without temp variable
int a = 10;
int b = 20;
// method 1 : using arithmatic operator
a = a + b;
b = a - b;
a = a - b;
// method 2 : using bitwise operator
a = a ^ b;
b = a ^ b;
a = a ^ b;
#
Problem Name
Practice
Solution
38
Find the two non-repeating elements in an array of repeating elements
voidbubbleSort(int arr[], int n){
for (int i = 0; i < n-1; i++){
bool flag = true;
for (int j = 0; j < n-1; j++){
if (arr[j] > arr[j+1]){
swap(arr[j],arr[j+1]);
flag = false;
}
}
if (flag) break;
}
}
Insertion Sort
Time - O(N2)
Space - O(1)
Stable
Iterative
Inplace
voidinsertionSort(int arr[], int n){
int val, j;
for (int i = 1; i < n; i++){
val = arr[i];
j = i;
while(j>0 && arr[j-1] > val){
arr[j] = arr[j-1];
j--;
}
arr[j] = val;
}
}
voidmergeSort(int arr[], int n){
if (n < 2) return;
int mid = n/2;
int left[mid];
int right[n - mid];
for (int i = 0; i < mid; i++){
left[i] = arr[i];
}
for (int i = mid; i < n; i++){
right[i-mid] = arr[i];
}
mergeSort(left, mid);
mergeSort(right, n-mid);
margeArray(left, right, arr, mid, n-mid);
}
intpartition(int arr[], int start, int end){
int pivot = arr[end];
int j = start;
for (int i = start; i < end; i++){
if (arr[i] <= pivot){
swap(arr[i], arr[j]);
j++;
}
}
swap(arr[end], arr[j]);
return j;
}
voidquickSort(int arr[], int start, int end){
if (start >= end) return; // base conditionint pivot = partition(arr, start, end);
quickSort(arr, start, pivot-1); // left arrquickSort(arr, pivot+1, end); // right arr
}