Find unique numbers in the vector if there is ONLY one element that is unique
#include <vector>
#include <accumulate>
std::vector <int> v {1,2,1,1,1,1,1,1,1,1,1};
int u = std::accumulate(v.begin(), v.end(), (uint32_t)0, [](uint32_t a, uint32_t b) { return a ^ b; });
// The reason this works is because xoring the number with itself is 0 and xroing number with 0 is itself.
>> 2
Various other algorithms based on vector
- segregate positive and negative numbers in the vector
- find max in array
- find minimum index in a rotated array
- plain vanilla binary search
- find maximum in array increases first then decreases
- search in bitonic array i.e. increasing and then decreasing array.
#include <iostream>
#include <vector>
#include <random>
#include <functional>
#include <numeric>
#include <algorithm>
using it = std::vector<int>::iterator;
// segregate positive and negative numbers in the vector
// the negative numbers should be at the start and positive
// numbers should be at the end
void segregate(it start, it finish){
while(true){
for(;*start < 0 && start < finish; start++){}
for(;*finish > 0 && start < finish; finish--){}
if(start < finish){
std::iter_swap(start, finish);
}else{
break;
}
}
}
// find max in an array
int find_max(it start, it finish, int max_num){
if(std::next(start) == finish) return std::max(*start, *finish);
it mid = start;
std::advance(mid, std::distance(start,finish)/2);
int max_left = find_max(start, mid, *start);
int max_right = find_max(mid, finish, *mid);
return std::max(max_left, max_right);
}
// find max sum subarray of size = k
int max_sum_k(it start, it finish, int k){
int max_so_far = 0, sum_of_k = 0;
for(;start < finish && start+k < finish;start++){
sum_of_k = std::accumulate(start,start+k, 0,std::plus<int>());
max_so_far = std::max(sum_of_k, max_so_far);
}
return max_so_far;
}
// find minimum index in a rotated array
int min_idx_rotated_ary(it start, it finish){
it orig_start = start;
if(*start < *std::prev(finish)) return 0;
while(start < finish){
it mid = start;
std::advance(mid, std::distance(start, finish)/2);
if (mid < finish && *mid > *std::next(mid)) {
return std::distance(orig_start, mid + 1);
}else if (*start <= *mid){
start = std::next(mid);
}else{
finish = std::prev(mid);
}
}
return 0;
}
// plain vanilla binary search
int binary_search(it start, it finish, int num){
int idx = -1;
it orig_start = start;
if(start > finish) return -1;
while(start <= finish){
it mid = start;
std::advance(mid, std::distance(start, finish)/2);
if(*mid == num){
idx = std::distance(orig_start, mid);
break;
}else if(num < *mid){
finish = std::prev(mid);
}else{
start = std::next(mid);
}
}
return idx;
}
// search an element using binary search in a rotated array
int bin_search_sorted_rotated_ary(it start, it finish, int num){
it orig_start = start;
int idx = -1;
while(start < finish){
it mid = start;
std::advance(mid, std::distance(start, finish)/2);
if(*mid == num){
idx = std::distance(orig_start, mid);
}
if(*start <= *mid){
if(*start <= num && num <= *mid){
finish = std::prev(mid);
}else{
start = std::next(mid);
}
}else{
if(*mid <= num && num <= *finish){
start = std::next(mid);
}else{
finish = std::prev(mid);
}
}
}
return idx;
}
// recursively find maximum in array increases first then decreases
int max_increasing_decreasing_ary(it start, it finish){
if(start == finish){
return *start;
}
if(std::next(start) == finish){
return std::max(*start, *finish);
}
it mid = start;
std::advance(mid, std::distance(start, finish)/2);
if(*mid > *std::prev(mid) && *mid > *std::next(mid)){
return *mid;
}
if(*mid > *std::next(mid) && *mid < *std::prev(mid)){
return max_increasing_decreasing_ary(start, std::prev(mid));
}else{
return max_increasing_decreasing_ary(std::next(mid), finish);
}
}
// {2,4,6,8,10,12,14,40,11,7,5,3,1}
// search = 40
int search_bitonic_ary(it start, it finish, int num){
int max = max_increasing_decreasing_ary(start, finish);
ptrdiff_t pos = std::distance(start, std::find(start, finish, max));
int idx = -1;
it orig_start = start;
if(max == -1){
return -1;
}
idx = binary_search(start, start+pos, num);
if(idx == -1){
start = start+pos;
while(start <= finish){
it mid = start;
std::advance(mid, std::distance(start, finish)/2);
if(*mid == num){
idx = std::distance(orig_start, mid);
break;
}else if(num > *mid){
finish = std::prev(mid);
}else{
start = std::next(mid);
}
}
}
return idx;
}
int main(){
std::vector<int> numbers {-1, 3, 8, -4, 5, -6, 7, -20, 30, -40};
segregate(numbers.begin(), numbers.end());
for(const int & i: numbers) std::cout << i << ' ';
std::cout << '\n';
std::random_device rd; //Will be used to obtain a seed for the random number engine
std::mt19937 gen(rd()); //Standard mersenne_twister_engine seeded with rd()
std::uniform_int_distribution<> dis(1, 200);
std::vector<int> nums_find_max {8, 4, 2, 1};
for (int n=0; n<20; ++n){
int num = dis(gen);
std::cout << num << ' ';
nums_find_max[n] = num;
}
std::cout << '\n';
std::cout << "Max number is : " << find_max(nums_find_max.begin(),
nums_find_max.end(),
*nums_find_max.begin()) << '\n';
std::vector<int> v_max_k{11, -8, 16, -7, 24, -2, 3};
std::cout << max_sum_k(v_max_k.begin(), v_max_k.end(), 3) << '\n'; // 33
std::vector<int> rotated{65, 70, 80, 90, 10, 20, 30, 40, 50, 60};
std::cout << min_idx_rotated_ary(rotated.begin(), rotated.end()) << '\n';
std::vector<int> bin_search{10, 20, 30, 40, 50, 60, 65, 70, 80, 90};
std::cout << binary_search(bin_search.begin(), bin_search.end(), 70) << '\n';
std::cout << binary_search(bin_search.begin(), bin_search.end(), 100) << '\n';
std::cout << bin_search_sorted_rotated_ary(rotated.begin(), rotated.end(), 80) << '\n';
std::cout << bin_search_sorted_rotated_ary(rotated.begin(), rotated.end(), 65) << '\n';
std::cout << bin_search_sorted_rotated_ary(rotated.begin(), rotated.end(), 30) << '\n';
std::vector<int> increasing_decreasing_ary{2,4,6,8,10,12,14,40,11,7,5,3,1};
std::cout << "max in increasing and then decreasing ary :" << max_increasing_decreasing_ary(increasing_decreasing_ary.begin(),
increasing_decreasing_ary.end()) << '\n';
std::cout << "index of 40 in bitonic_ary "<<search_bitonic_ary(increasing_decreasing_ary.begin(),
increasing_decreasing_ary.end(),
40) << '\n';
std::cout << "index of 7 in bitonic_ary " << search_bitonic_ary(increasing_decreasing_ary.begin(),
increasing_decreasing_ary.end(),
7) << '\n';
}
Print matrix diagonally
#include <iostream>
#include <vector>
int main(){
std::vector<std::vector<int>> v(8, std::vector<int>(8, 0));
for(int i = 0; i < 8; i++){
for(int j = 0; j < 8; j++){
v[i][j]= (i+1)*(j+1);
}
}
// printing the matrix
for(int i = 0; i < 8; i++){
for(int j = 0; j < 8; j++){
std::cout << v[i][j] << '\t';
}
std::cout << '\n';
}
int row, col;
int rowCount = v.size();
int columnCount = v[0].size();
for(int k = 0; k < rowCount; k++){
for(row = k, col = 0; row >= 0 && col <= columnCount; row --, col++){
std::cout << v[row][col] << '\t';
}
std::cout << '\n';
}
for(int k = 0; k < rowCount; k++){
for(row = rowCount -1, col = k; row >= 0 && col <= columnCount; row --, col++){
std::cout << v[row][col] << '\t';
}
std::cout << '\n';
}
return 0;
}
Matrix:
1 2 3 4 5 6 7 8 2 4 6 8 10 12 14 16 3 6 9 12 15 18 21 24 4 8 12 16 20 24 28 32 5 10 15 20 25 30 35 40 6 12 18 24 30 36 42 48 7 14 21 28 35 42 49 56 8 16 24 32 40 48 56 64
Expected Output:
1 2 2 3 4 3 4 6 6 4 5 8 9 8 5 6 10 12 12 10 6 7 12 15 16 15 12 7 8 14 18 20 20 18 14 8 8 14 18 20 20 18 14 8 16 21 24 25 24 21 16 0 24 28 30 30 28 24 3 32 35 36 35 32 4 40 42 42 40 5 48 49 48 6 56 56 7 64 8
Supercharged Computing 