Posts

Recursion

Image
  Write a recursive function to find Maximum in an array.       // Example program #include <iostream> #include <bits/stdc++.h> int findMax(int* A, int i){ if(i==0){ return A[i]; } int max_in_subproblem = findMax(A, i-1); return std::max(A[i],max_in_subproblem); } int main() { int a[10] = {8,6,5,2,9,3,10,1,4,7}; int maximum = findMax(a, 9); std::cout << maximum; } // Example program #include <iostream> #include <string> int factorial(int n){ if(n==0 || n==1){ return 1; } int fact = factorial(n-1); return n * fact; } int main() { int fact = factorial(9); std::cout<< fact; } Write a recursive function to calculate Nth term of Fibonacci. #include <iostream> #include <string> int fibonacci(int n){ if(n==0 || n==1){ return 1; } int fib = fibonacci(n-1) + fibonacci(n-2); return n * fib; } int main() { int fib = fibona...
Post a Comment
Read more

Largest Sum Contiguous Subarray

  #include <iostream> #include <vector> using namespace std; int partial_sum(vector<int>& sum, int x, int y) { return sum[y] - sum[x - 1]; } void sum_array(vector<int>& v, vector<int>& sum) { sum.push_back(v[0]); for (auto i = 1; i < v.size(); i++) { sum.push_back(sum[i - 1] + v[i]); } } int max_sum_subarray(vector<int>& sum) { int minSum = 0; int result = INT_MIN; for (int r = 0; r < sum.size(); r++) { if (sum[r] - minSum > result) { result = sum[r] - minSum; } if (sum[r] < minSum) { minSum = sum[r]; } } return result; } int main() { vector<int> v = { -2, -3, 4, -1, -2, 1, 5, -3 }; vector <int> sum; sum_array(v, sum); cout << max_sum_subarray(sum); return 0; }
Post a Comment
Read more

Partial Sum

  #include <iostream> #include <vector> using namespace std; int partial_sum(vector<int>& sum, int x, int y) { return sum[y] - sum[x - 1]; } void sum_array(vector<int>& v, vector<int>& sum) { sum.push_back(v[0]); for (auto i = 1; i < v.size(); i++) { sum.push_back(sum[i - 1] + v[i]); } } int main() { vector<int> v = { 7, 3, 5, 6, 7, 9, 3, 5, 11 }; vector <int> sum; sum_array(v, sum); // for (auto i = sum.begin(); i != sum.end(); i++) // cout << *i << " "; cout << partial_sum(sum, 3, 7); return 0; }
Post a Comment
Read more

Advancing through an Array

  #include <iostream> #include <vector> using namespace std; bool canReachEnd(vector<int>& v) { int last_index = v.size()-1; int furthest_index = 0; for (int i = 0; i <= furthest_index && furthest_index < last_index; i++) { furthest_index = max(furthest_index, i + v[i]); } return (furthest_index >= last_index); } int main() { vector<int> v = { 3,2,0,0,2,0,1 }; bool result = canReachEnd(v); if (result) { cout << "We can reach the end of array.\n"; } else { cout << "We can't reach the end of array.\n"; } }
Post a Comment
Read more

Dutch Flag Problem

  #include <iostream> #include <vector> using namespace std; void dutchFlag(vector<int>& v, int pivot) { int smaller = 0; int equal = 0; int larger = v.size() - 1; while (equal < larger) { if (v[equal] < pivot) { swap(v[smaller++], v[equal++]); } else if (v[equal] == pivot) { equal++; } else { swap(v[larger--], v[equal]); } } } /*void dutchFlag(vector<int>& v, int pivot) { int smaller = 0; for (int i = 0; i < v.size(); i++) { if (v[i] < pivot) { swap(v[i], v[smaller++]); } } int larger = v.size() - 1; for (int i = v.size() - 1; i >= 0 && v[i] >= pivot; i--) { if (v[i] > pivot) { swap(v[i], v[larger--]); } } }*/ /* void dutchFlag(vector<int>& v, int pivot) { for (int i = 0; i < v.size(); i++) { for (int j = i + 1; j ...
Post a Comment
Read more

Even Odd problem

#include <iostream> #include <vector> using namespace std; void evenOdd(vector<int> &v) { int next_even = 0; int next_odd = v.size() - 1; while (next_even < next_odd) { if (v[next_even] % 2 == 1) { swap(v[next_even], v[next_odd--]); } else { next_even++; } } } int main() { vector<int> v = { 1, 2, 3 , 4, 5, 6, 7}; evenOdd(v); for (auto i = v.begin(); i != v.end(); i++) cout << *i << " "; return 0; }
Post a Comment
Read more

Swap bits at ith and jth position of integer n

  #include <iostream> using namespace std; //function to swap bits of an integer n unsigned swapBit(unsigned int n, unsigned int i, unsigned int j) { if(( n & (1 << (i-1))) != (n & (1 << (j-1)))){ n ^= (1 << (i-1)) ^ (1 << (j-1)); } return n; } int main() { unsigned int n = 7, i = 1, j = 4 ; unsigned int result = swapBit(n,i,j); cout << "After swapping the bit at position "<< i <<" and "<< j << " of integer "<< n << ", we get "<< result<<"." << endl; return 0; }
Post a Comment
Read more