# Modern c++ std::vector algorithms

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;
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;
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;
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;

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;

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;
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```

## Author: Saurabh Purnaye

VP - Low Latency Developer @jpmchase... Linux, C++, Python, Ruby. pursuing certificate in #QuantFinance and Passed CFA L1