misc.cc

#include <iostream>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <sstream>
#include <climits>
#include <bits/stdc++.h>
using namespace std;


//print fibonacci numbers


 void print(int *a, int num) {
     
     for (int i = 0; i < num; i++) {
         cout << " " << a[i];
     }
     
     
     cout << endl;
     
 }

template <typename T>
void print_bits ( T val, std::ostream& out )
{
  T n_bits = sizeof ( val ) * CHAR_BIT;
  for (int i = n_bits - 1; i >= 0;  i-- ) {
    out << (val & (1 << i));
   // val >>= 1;
  }
}


template <typename T>
T rev_bits ( T val ) {
  T ret = 0;
  T n_bits = sizeof ( val ) * CHAR_BIT;

  for ( unsigned i = 0; i < n_bits; ++i ) {
    ret = ( ret << 1 ) | ( val & 1 );
    val >>= 1;
  }

  return ret;
}


void merge(int* a, int left, int right) {
    int mid = (right - left)/2;
    
    int i1 = 0;
    int i2 = left;
    int i3 = mid +1;
    
    int temp [right - left + 1];
    
    cout << "merge: " << left << " " << right << endl; 
    
    while (i2 <= mid && i3 <= right) {
        
        if (a[i2] < a[i3]) {
            temp[i1++] = a[i2++];
        } else {
            temp[i1++] = a[i3++];
        }
    }
    
    
    while (i2 <= mid) {
        temp[i1++] = a[i2++];
    }
    
    while (i3 <= right) {
        temp[i1++] = a[i3++]; 
    }
    
    
    for (int i = left; i<= right; i++ ) {
        a[i] = temp[i - left];
        
    }
    
}


 void merge_sort(int* a, int left, int right) {
     if (left < right) {
         
        cout << "merge_sort:" << left << " " << right << endl; 
        int mid = (right - left)/2;
        merge_sort(a, left, mid);
        merge_sort(a, mid+1, right);
        merge(a, left, right); 
     }
 }
  

void print_bits(int num) {
    cout << "printing bits of " << num << endl;
    for (int i = 8*sizeof(num) - 1 ; i >= 0 ; i--) {
        char a = (num & (1 << i)) ? '1' : '0';
        cout << a;
    }
    
    cout << endl;
}

void set_bit(int& value, int bit_num) {
    value = value | (1 << bit_num);
}

void set_all_bits_after_i(int& value, int i) {
    value = value | ~((1 << i +1) - 1); 
}


void unset_bit(int& value, int bit_num) {
    value = value & ~(1 << bit_num);
}



char* reverse(char* str) {
    char* end = str;
    
    while(*end) {
        end++;
    }
    
    --end;
    
    cout << "end = " << *end << endl;
    
    char tmp;
    while (str < end) {
        tmp = *str;
        *str++ = *end;
        *end-- =tmp;
        
    }
    
}


int max_value(string str) {
    
    int res = str[0] - '0';
    
    for (int i = 1; i < str.length(); i++) {
        int num = str[i] - '0';
        int prev = str[i-1] - '0';
        
        cout << "res " << res << endl;
        
        if (num == 0 || num == 1 || prev == 0 || prev == 1) {
            res += num;
        } else {
            res *= num;
        }    
    }
    
    return res;
    
}


bool zero_sum(int arr[], int n, int sum) {
    std::unordered_map<int, bool> hash_map;
    
    int curr_sum = 0;

    for (int i = 0; i < n; i++) {
        curr_sum += arr[i];
        if (arr[i] == 0 || hash_map[curr_sum] == true) {
            return true;
        }
        
        hash_map[curr_sum] = true;
    }
    
    return false;
}


/* Returns true if the there is a subarray of arr[] with sum equal to 'sum'
   otherwise returns false.  Also, prints the result */
int subArraySum(int arr[], int n, int sum)
{
    /* Initialize curr_sum as value of first element
       and starting point as 0 */
    int curr_sum = arr[0], start = 0, i;
 
    /* Add elements one by one to curr_sum and if the curr_sum exceeds the
       sum, then remove starting element */
    for (i = 1; i < n; i++)
    {
        // If curr_sum exceeds the sum, then remove the starting elements
        while (curr_sum > sum && start < i-1)
        {
            curr_sum = curr_sum - arr[start];
            start++;
        }
 
        // If curr_sum becomes equal to sum, then return true
        if (curr_sum == sum)
        {
            printf ("Sum found between indexes %d and %d", start, i-1);
            return 1;
        }
 
        // Add this element to curr_sum
        curr_sum = curr_sum + arr[i];
    }
 
    // If we reach here, then no subarray
    printf("No subarray found");
    return 0;
}

int max_summ(int arr[], int n) {
    int max_sum = 0, cur_sum = 0;
    
    cur_sum = arr[0];
    for (int i = 1; i < n ;i++) {       
        cur_sum = max(arr[i], cur_sum + arr[i]);
        max_sum = max(cur_sum, max_sum);
        cout << "cur " << cur_sum << " max " << max_sum << endl;

    }
    
    return max_sum;
}


int main() {
    
    const int num = 10;
   // int arr[10] = { 1, 3, 2, 5, 4, 9, 8, 6 ,7, 10 };
    
   // print(arr, num);
    
    int aaar[20] = {0};
    
    int arr[] = {15, 2, 4, -21, 9, 5, 10, -1};
    
    cout << "max sum: " << max_summ(arr, sizeof(arr)/sizeof(int)) << endl;
    
    
    cout << "max element " << *std::max_element(arr, arr + sizeof(arr)/sizeof(int)) << endl;
    int n = sizeof(arr)/sizeof(arr[0]);
    int sum = 23;
    
    
    cout << "sub array " << subArraySum(arr, n, sum) << endl;
 
   // print(arr, num);
    
    int a = 2;
    a = 1;
    
    a = ~a +1;
    cout << a << endl;
    //rev_bits(a);
    print_bits(a);
    //reverse(str);
    //cout << str << endl;
    
    
    return 0;
}