## Iterators – look and say sequence algorithm

Look and say sequence is fun little exercise.. here is the code

```#include <iostream>
#include <vector>
#include <string>
#include <numeric>

std::string looknsay(int num){
// initialize vector with vector of ints.
// add default seed value to it [1].
std::vector<std::vector<int>> look_n_say_seq{{1}};
// iterate over until the number n is reached.
for(int n = 0; n <= num; n++){
auto latest_sequence = look_n_say_seq.back();
std::vector<int> next_sequence;
// keep a pair of iterators to move across the latest sequence from vector.
auto i = latest_sequence.begin();
auto j = latest_sequence.begin();
while(i < latest_sequence.end()){
for(;*i==*j && j < latest_sequence.end();++j){}
// distance will give the count
next_sequence.push_back(std::distance(i, j));
// *i will give the actual number to iterate on
next_sequence.push_back(*i);
i = j;
}
// insert newly created sequence into the vector.
look_n_say_seq.push_back(next_sequence);
}
auto latest_sequence = look_n_say_seq.back();
// accumulate - join vector of ints to make string and return
return std::accumulate(std::next(latest_sequence.begin()),
latest_sequence.end(),
std::to_string(*latest_sequence.begin()),
[](std::string s, int i){return s += std::to_string(i);});
}
int main(){
std::cout << looknsay(0) << '\n';
std::cout << looknsay(1) << '\n'; // 11
std::cout << looknsay(2) << '\n'; // 21
std::cout << looknsay(3) << '\n'; // 1211
std::cout << looknsay(4) << '\n'; // 111221
std::cout << looknsay(5) << '\n'; // 312211
}```

## std::queue operations

### Iteration:

Iteration is very basic and important operation of any container type like std::vector, std::deque or std::list.

```std::queue<int> q;
for(int i = 0; i <= 10; i++){
q.push(i);
}
for(int i = 0; i <= 10; i++){
std::cout << q.pop() << '\n';
}```

### Shuffle Queue:

Shuffling with extra space (using another deque)can be done as follows:

```#include <iostream>
#include <queue>
#include <algorithm>
#include <random>
#include <deque>

int main(){
std::queue<int> q;
for(int i = 0; i <= 10; i++){
q.push(i);
}

std::deque<int> d;
for(int i = 0; i <= 10; i++){
d.push_back(q.pop());
}

unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
std::shuffle (d.begin(), d.end(), std::default_random_engine(seed));

std::queue<int> empty;
std::swap(q, empty);

std::for_each(d.begin(), d.end(), [&q](const auto & i){q.push(i);});
std::for_each(d.begin(), d.end(), [&q](const auto & i){std::cout << i << '\n';});

for((int i = 0; i <= 10; i++){
std::cout << q.pop() << '\n';
}

}

```

## Linked list using smart pointers

I have observed and code several versions of linked lists and came with my own implementation of linked list. This linked list uses smart pointers and supports operations like insert after, insert before, reverse and print etc for the list.

```#include <iostream>
#include <memory>

template <typename T>
struct Node{
T value;
bool head = false;
std::shared_ptr<Node<T>> next;

Node(): head(true), value(-1){}; // head with -1 value
Node(T value): head(false), value(value){}; // node

next = std::make_shared<Node<T>>(value);
return next;
}
};

template<typename T>
struct List{
std::shared_ptr<Node<T>> tail;

List(){
}

tail = tail->next;
}

void print(){
std::cout << std::string(100, '-') << '\n';
auto current = head;
while(current != nullptr){
std::cout << current->value << '\t';
current = current->next;
}
std::cout << '\n' << std::string(100, '-') << '\n';
}

void reverse(){
auto current = head;
std::shared_ptr<Node<T>> next, prev;
while(current != nullptr){
next = current->next;
current->next = prev;
prev = current;
current = next;
}
}

void insert_after(T after_value, T value){
auto current = head;
while(current != nullptr){
if(current->value == after_value){
auto temp_next = current->next;
auto node = create_node(value);
current->next = node;
node->next = temp_next;
break;
}
current = current->next;
}
}

void insert_before(T before_value, T value){
auto current = head;
std::shared_ptr<Node<T>> prev;
while(current != nullptr){
if(current->value == before_value){
auto node = create_node(value);
node->next = current;
prev->next = node;
}
prev = current;
current = current->next;
}
}

std::shared_ptr<Node<T>> create_node(T value){
return std::make_shared<Node<T>>(value);
}
};

int main(){
List<int> l; // initialize the linked list

for(int i = 1; i <= 10; i++){
}
l.print();
l.reverse();
l.print();
l.reverse();
l.insert_after(1, 2);
l.print();
l.insert_before(8, 18);
l.print();
return 0;
}```

Output:

```g++ --std=c++17 linked_list.cpp -g -o linked_list && ./linked_list
-----------------------------------------------------------------------------------------------------
-1 1 2 3 4 5 6 7 8 9 10
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
10 9 8 7 6 5 4 3 2 1 -1
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
-1 1 2 2 3 4 5 6 7 8 9 10
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
-1 1 2 2 3 4 5 6 7 18 8 9 10
----------------------------------------------------------------------------------------------------```

## reverse in O(log n) time

The basic framework for divide and conquer algorithm can be used for any operations like reverse, checking if array is sorted etc. The possible implementation of reversing a string/vector is given as follows which takes O(n) time where n is size of collection string/vector.

```template<class BidirIt>
void reverse(BidirIt first, BidirIt last)
{
while ((first != last) && (first != --last)) {
std::iter_swap(first++, last);
}
}```

Better algorithm for this can be given as follows:

```#include <iostream>
#include <algorithm>
#include <string>

template <typename T>
void reverse_rotate(T first, T last){
if((first == last) || std::next(first) == last) return;
T middle = first;
reverse_rotate(first, middle);
reverse_rotate(middle, last);
std::rotate(first, middle, last);
}

int main(){
std::string s = "This is super cool";
reverse_rotate(s.begin(), s.end());
std::cout << s << '\n';
}```

## is_sorted in O(log n) time

Checking if array is sorted is simple, compare consecutive elements to check if next element is greater than the previous element. This takes O(n) time. The possible implementation of std::is_sorted is given as follows:

```template <class ForwardIterator>
bool is_sorted (ForwardIterator first, ForwardIterator last)
{
if (first==last) return true;
ForwardIterator next = first;
while (++next!=last) {
if (*next<*first) // or, if (comp(*next,*first)) for version (2)
return false;
++first;
}
return true;
}```

Here I came with an algorithm which is like quick sort and uses O(log n) time. Here is the implementation.

```#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

template <typename T>
bool check_sorted(T start, T finish, bool sorted = true){
if(start == finish) return true;

if(std::next(start) == finish) return *start <= *finish;

T middle = start;

sorted &= check_sorted(start, middle);
sorted &= check_sorted(middle, finish-1);
return sorted;
}

int main(){
std::vector<int> v(20);
std::iota(v.begin(), v.end(), 1);
bool sorted = check_sorted(v.begin(), v.end());
std::cout << "v is sorted? : " << sorted << '\n';

std::vector<int> v2 {20, 1, 3, 5, 2, 1, 4, 19, 18, 10};
sorted = check_sorted(v2.begin(), v2.end());
std::cout << "v2 is sorted?: " << sorted << '\n';

std::vector<int> v3 {1,1,1,1,1,1,1,1,1,1,1,1,1,1};
sorted = check_sorted(v3.begin(), v3.end());
std::cout << "v3 is sorted?: " << sorted << '\n';

std::vector<int> v4 {10,1,1,1,1,1,1,1,1,1,1,1,1,1};
sorted = check_sorted(v4.begin(), v4.end());
std::cout << "v4 is sorted?: " << sorted << '\n';
}```

## Remove dups in sorted vector

To remove duplicates of an array, use a hash map and array elements as keys, then extract keys. This requires extra space for storing the hash and time. Following algorithm does not need any extra space and time.

The algorithm is uses 3 iterators and moves the duplicate elements at the start of vector and erases the rest of vector. Pseudo code given as follows:

1. take iterator ​`​start` that points to beginning of vector.
2. take another iterator `i` that points to next element to start.
3. move  i to next index until elements are duplicate.
4. replace start with next element and increase start pointer.
5. at the end erase elements from start+1 to end from vector.
```#include <iostream>  // std::cout
#include <vector>
#include <cstdlib>  // std::srand
#include <ctime>    // std::time

int main(){
std::vector<int> v(100);
std::srand(std::time(nullptr)); // use current time as seed for random generator

// generate 1000 random numbers between 0 to 99
for(int i = 0; i < 1000; i++){
int random_variable = std::rand()%100;
v.push_back(random_variable);
std::cout << random_variable << ' ';
}

// sort
std::sort(v.begin(), v.end());

std::vector<int>::iterator start = v.begin();
std::vector<int>::iterator end = v.end();
auto i = start+1; // std::vector<int>::iterator i = start+1;
while(i != end-1){
if(*start == *i){
i++;
}else{
start++;
*start = *i;
}
}

v.erase(start+1, end);
for(const auto & i:v) std::cout << i << ' ';
}```

## Count ones in binary representation

The task is to find ones in the binary representation of a number in given range. For an example: 1 is represented a 1 in binary so the number is 1’s in 1 is 1. Another example: 4 is represented as 100 in binary so number of 1’s in binary representation of 4 is 1.

In order to find 1’s in a very large range between 1 and 10,000,000 sounds complicated but can solved with following algorithm

```#include <iostream>
#include <algorithm>
#include <cmath>

long long ccb(int col, int n) {
double division = (n + 1) / double(2 << col);
int sum = static_cast<int>(division);
long long rest = std::max(0.0, (division - sum) * (2 << col) - (1 << col));
return sum * (1 << col) + rest;
}

long long cab(int n) {
long long bits = 0;
for (int i = 0; i < 30; i++) {
bits += ccb(i, n);
}
return bits;
}

long long countOnes(int left, int right) {
return cab(right) - cab(left - 1);
}```

## Multiply large numbers as strings

This algorithm is very much like factorial. Multiplication of very large numbers represented as strings because they go out of the integer range.

```#include <iostream>
#include <vector>
#include <string>
#include <sstream>

std::string multiply(std::string a, std::string b) {
// take a vector of length 200 and initialize all of its elements to 0.
std::vector<int> multiplication(200, 0);

int place = 0;
for(int i = a.size() - 1 ; i >= 0; i--){
int carry = 0;
std::vector<int>::iterator it = multiplication.begin() + place;
for(int j = b.size() - 1 ; j >= 0; j--){
int a_element = a[i] - '0';
int b_element = b[j] - '0';
int prod = a_element*b_element + carry + *it;
*it = prod % 10;
carry = prod / 10;
it++;
while (carry){
int current_carry = carry + *it;
*it += current_carry % 10;
it++;
carry = current_carry / 10;
}
}
place++;
}

std::stringstream ss;
for(int i = multiplication.size(); i >= 0; i--){
ss << multiplication[i];
}
return ss.str();
}```

## Reverse a number

Algorithm for reversing the number is as follows:

```#include <cmath> // for finding out the length of number

// find the length of the number to find out the highest power of 10
// then divide the number by 10 and take remainder to find digit
// at the unit's place.
// multiply the digit with power of 10. repeat length times.
int reverse(int x) {
int length = (int)log10(abs(x)); // magic formula to find length
int reversed = 0;
int remainder = 0;
for(int i = length; i > 0 ; --i){
remainder = x % 10;
x = x / 10;
reversed += remainder * pow(10, i);
}
reversed += x;
return reversed;
}```

## Factorial of a large number

Factorial of an integer is found by multiplying all the numbers starting from 1 up to the number. So factorial for 5 is 5! = 5 x 4 x 3 x 2 x 1 = 120.

A recursive algorithm for finding factorial is given as

```int factorial(int num){
return num > 1 ? : num * factorial(num - 1) : 1;
}```

The issue is factorial quickly grows out of the range of int/double/float limit.

Example:

factorial of 100 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

factorial of 1000 402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Following is program I wrote to find factorials and store them as strings instead of numbers.

```#include <iostream> // for cout
#include <vector> // used to store the numbers
#include <string>
#include <sstream>

// method to multiply each number passed with each element
// within the vector. If there is a carry, just add it to the next
// number.
void multiply_vector(std::vector<int> & v, int multiply_num){
int carry = 0;
for(size_t i = 0; i < v.size(); i++){
int prod = v[i] * multiply_num + carry;
v[i] = prod % 10;
carry = prod / 10;
}

while (carry)
{
int current_carry = carry % 10;
v.push_back(current_carry);
carry = carry / 10;
}
}

// instead of recursion use loop and vector to store result
// of multiplication
std::string factorial(int num){
std::vector<int> factorial_digits;
factorial_digits.push_back(1);
for(int i = 2; i <= num; i++){
multiply_vector(factorial_digits, i);
}

// received the result in vector but need to reverse it..
std::stringstream ss;
for(int i = factorial_digits.size()-1; i >= 0; i--){
ss << factorial_digits[i];
}
return ss.str();
}

int main(){
// find factorial of 1000
std::cout << factorial(1000) << '\n';
return 0;
}```