Modern c++ std::vector algorithms

dhruv-deshmukh-266273-unsplash

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

Author: Saurabh Purnaye

Sr. Developer @NYSE @ICE_Markets. Low Latency Trading, Linux, C++, Python, Ruby. pursuing certificate in #QuantFinance and Passed CFA L1

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s