Find maximum average subarray of k length

#include using namespace std; int maxAverageSubarray(int a[], int alen, int k) { if(alen < k) return -1; int max_sum = 0; for(int i=0;i max_sum) { max_sum = sum; index = i; } } return index-k+1; } int main() { // your code goes here int arr[] = {1, 12, -5, -6, 50, 3}; int k = 4; int n = sizeof(arr)/sizeof(arr[0]); cout << "The maximum average subarray of " "length "<< k << " begins at index " << maxAverageSubarray(arr, n, k); return 0; }

Substring in a given string

#include #include using namespace std; int substrpos(char s[], char t[]) { if(( (!s) || (!t) || strlen(s) < strlen(t)) ) return -1; for(int i=0; i<(strlen(s)-strlen(t))+1; i++) { int j=0; for(;j

Segregate 0s and 1s in an array

#include using namespace std; void groupZeroOne(int a[], int len) { int left = 0; int right = len-1; while(left < right) { if(a[left] == 1) { while(right > left && a[right] == 1) right--; int t=a[left]; a[left] = a[right]; a[right] = t; left++; right--; } else left++; } } void printArray(int a[], int len) { for(int i=0;i

Sort an array of 0s, 1s and 2s

#include using namespace std; void printArray(int a[], int len) { for(int i=0;i left && a[right] == val) right--; int t=a[left]; a[left] = a[right]; a[right] = t; left++; right--; } else left++; } if(a[right] == val) right--; return right; } int main() { // your code goes here int a[] = {1,0,2,0,1,2,1,2,0,1,1}; cout << "before arrangement- "; printArray(a, sizeof(a)/sizeof(int)); int twoIndex = groupZeroOneTwo(a, sizeof(a)/sizeof(int) - 1, 2); cout << "after arrangement1- "; printArray(a, sizeof(a)/sizeof(int)); groupZeroOneTwo(a, twoIndex, 1); cout << "after arrangement2- "; printArray(a, sizeof(a)/sizeof(int)); return 0; }

Count all distinct pairs with difference equal to k

#include #include using namespace std; void printArray(int a[], int len) { for(int i=0;i k) l++; } cout << "count =" << count; } int main() { // your code goes here int a[] = {8, 12, 16, 4, 0, 20}; cout << "array - "; printArray(a, sizeof(a)/sizeof(a[0])); countPairsWithDiffK(a, sizeof(a)/sizeof(a[0]), 4); return 0; }

sort an array using quicksort

#include #include using namespace std; void printArray(int a[], int len) { for(int i=0;i=r) return; //choose pivot int m = l; //this loop brings all elements < a[l] within m and > a[l] from m+1 to r for(int i=l+1; i<=r; i++) { if(a[i] < a[l]) { m++; int t=a[i]; a[i] = a[m]; a[m] = t; } } //move a[l] to pivot position which will make it rightly positioned in the array int t = a[m]; a[m] = a[l]; a[l] = t; qksort(a, l, m-1); qksort(a, m+1, r); } int main() { // your code goes here int a[] = {8, 12, 16, 4, 0}; cout << "before sorting - "; printArray(a, sizeof(a)/sizeof(a[0])); qksort(a, 0, sizeof(a)/ sizeof(a[0]) - 1); cout << "after sorting - "; printArray(a, sizeof(a)/sizeof(a[0])); return 0; }

Minimum length unsorted array

#include using namespace std; void printArray(int a[], int len) { for(int i=0;i a[i+1]) { left = i; break; } } if(left == -1) { cout << "arary is sorted"; return; } for(int i=n-1; i>left; i--) { if(a[i] < a[i-1]) { right = i; break; } } int min=a[left]; int max=a[left]; for(int i=left+1; i<=right; i++) { if(a[i] < min) min = a[i]; if(a[i] > max) max = a[i]; } for(int i=0;i min) { left = i; break; } } for(int i=n; i>right-1; i--) { if(a[i] < max) { right = i; break; } } cout << "left =" << left << " right=" << right << endl; } int main() { // your code goes here int a[] = {10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60}; cout << "array - "; printArray(a, sizeof(a)/sizeof(int)); minLengthUnsortedSubArray(a, sizeof(a)/sizeof(int)); return 0; }

Maximum sum sub matrix

 #include <iostream>

using namespace std;

void resetArray(int a[], int row)

{

    for(int i=0; i<row; i++)

    {

        a[i] = 0;

    }

}

void printMatrix(int a[4][4], int maxleft, int maxright, int maxup, int maxdown)

{

    cout << "\n";

    for(int i=maxup; i<=maxdown; i++)

    {

        for(int j=maxleft; j<= maxright; j++)

        {

            cout << a[i][j] << " ";

        }

        cout << endl;

    }

}

void maxSumSubMatrix(int a[4][4], int row, int col)

{

    int sum = 0, maxSum = 0;

    

    int sumColumn[row];

    int maxleft = 0, maxright = 0,  maxup = 0, maxdown = 0;

    int curup = 0;

    

    for(int i=0; i<col; i++)

    {

        resetArray(sumColumn, row);

        for(int j=i; j<col; j++)

        {

            sum = 0;

            curup = 0;

            for(int k=0; k<row; k++)

            {

                // cout << endl << sumColumn[k] << " + " << a[k][j] << "=";

                sumColumn[k] += a[k][j];

                // cout << sumColumn[k];

                sum += sumColumn[k];

                // cout << "  sumsofar=" << sum ;

                if(sum > maxSum)

                {

                    maxSum = sum;

                    maxleft = i;

                    maxright = j;

                    maxdown = k;

                    maxup = curup;

                    

                    // cout << " i:" << i << " j:" << j;

                    // cout << " maxsum:" << maxSum << " sum:" << sum;

                    // cout << " maxleft:" << maxleft << " maxright:" << maxright;

                    // cout << " maxup:" << maxup << " maxdown:" << maxdown << endl;

                }

                else if(sum <= 0)

                {

                    sum = 0;

                    curup = k+1;

                }                

            }

        }

    }

    

    printMatrix(a, maxleft, maxright, maxup, maxdown);

}

int main() {

// your code goes here

int a[4][4] = {

        1, -2,-1, 3,

        3,-6, 7, -4,

   -5, 3, 0, 2,

    -4, 5,-2, 1

};

printMatrix(a, 0, 3, 0, 3);

cout << "Maximum sum sub matrix is: " << endl;

maxSumSubMatrix(a, 4, 4);

return 0;

}