Given a matrix of ‘O’ and ‘X’, replace ‘O’ with ‘X’ if surrounded by ‘X’

Given a matrix where every element is either ‘O’ or ‘X’, replace ‘O’ with ‘X’ if surrounded by ‘X’. A ‘O’ (or a set of ‘O’) is considered to be by surrounded by ‘X’ if there are ‘X’ at locations just below, just above, just left and just right of it.

Examples:

Input: mat[M][N] =  {{'X', 'O', 'X', 'X', 'X', 'X'},
                     {'X', 'O', 'X', 'X', 'O', 'X'},
                     {'X', 'X', 'X', 'O', 'O', 'X'},
                     {'O', 'X', 'X', 'X', 'X', 'X'},
                     {'X', 'X', 'X', 'O', 'X', 'O'},
                     {'O', 'O', 'X', 'O', 'O', 'O'},
                    };
Output: mat[M][N] =  {{'X', 'O', 'X', 'X', 'X', 'X'},
                      {'X', 'O', 'X', 'X', 'X', 'X'},
                      {'X', 'X', 'X', 'X', 'X', 'X'},
                      {'O', 'X', 'X', 'X', 'X', 'X'},
                      {'X', 'X', 'X', 'O', 'X', 'O'},
                      {'O', 'O', 'X', 'O', 'O', 'O'},
                    };

Input: mat[M][N] =  {{'X', 'X', 'X', 'X'}
                     {'X', 'O', 'X', 'X'}
                     {'X', 'O', 'O', 'X'}
                     {'X', 'O', 'X', 'X'}
                     {'X', 'X', 'O', 'O'}
                    };
Input: mat[M][N] =  {{'X', 'X', 'X', 'X'}
                     {'X', 'X', 'X', 'X'}
                     {'X', 'X', 'X', 'X'}
                     {'X', 'X', 'X', 'X'}
                     {'X', 'X', 'O', 'O'}
                    };

This is mainly an application of Flood-Fill algorithm. The main difference here is that a ‘O’ is not replaced by ‘X’ if it lies in region that ends on a boundary. Following are simple steps to do this special flood fill.

1) Traverse the given matrix and replace all ‘O’ with a special character ‘-‘.

2) Traverse four edges of given matrix and call floodFill(‘-‘, ‘O’) for every ‘-‘ on edges. The remaining ‘-‘ are the characters that indicate ‘O’s (in the original matrix) to be replaced by ‘X’.

3) Traverse the matrix and replace all ‘-‘s with ‘X’s.

Let us see steps of above algorithm with an example.
Let following be the input matrix.

       mat[M][N] =  {{'X', 'O', 'X', 'X', 'X', 'X'},
                     {'X', 'O', 'X', 'X', 'O', 'X'},
                     {'X', 'X', 'X', 'O', 'O', 'X'},
                     {'O', 'X', 'X', 'X', 'X', 'X'},
                     {'X', 'X', 'X', 'O', 'X', 'O'},
                     {'O', 'O', 'X', 'O', 'O', 'O'},
                    };

Step 1: Replace all ‘O’ with ‘-‘.

       mat[M][N] =  {{'X', '-', 'X', 'X', 'X', 'X'},
                     {'X', '-', 'X', 'X', '-', 'X'},
                     {'X', 'X', 'X', '-', '-', 'X'},
                     {'-', 'X', 'X', 'X', 'X', 'X'},
                     {'X', 'X', 'X', '-', 'X', '-'},
                     {'-', '-', 'X', '-', '-', '-'},
                    };

Step 2: Call floodFill(‘-‘, ‘O’) for all edge elements with value equals to ‘-‘

       mat[M][N] =  {{'X', 'O', 'X', 'X', 'X', 'X'},
                     {'X', 'O', 'X', 'X', '-', 'X'},
                     {'X', 'X', 'X', '-', '-', 'X'},
                     {'O', 'X', 'X', 'X', 'X', 'X'},
                     {'X', 'X', 'X', 'O', 'X', 'O'},
                     {'O', 'O', 'X', 'O', 'O', 'O'},
                    };

Step 3: Replace all ‘-‘ with ‘X’.

       mat[M][N] =  {{'X', 'O', 'X', 'X', 'X', 'X'},
                     {'X', 'O', 'X', 'X', 'X', 'X'},
                     {'X', 'X', 'X', 'X', 'X', 'X'},
                     {'O', 'X', 'X', 'X', 'X', 'X'},
                     {'X', 'X', 'X', 'O', 'X', 'O'},
                     {'O', 'O', 'X', 'O', 'O', 'O'},
                    };

The following is C++ implementation of above algorithm.

// A C++ program to replace all 'O's with 'X''s if surrounded by 'X'
#include<iostream>
using namespace std;
// Size of given matrix is M X N
#define M 6
#define N 6
// A recursive function to replace previous value 'prevV' at  '(x, y)'
// and all surrounding values of (x, y) with new value 'newV'.
void floodFillUtil(char mat[][N], int x, int y, char prevV, char newV)
{
    // Base cases
    if (x < 0 || x >= M || y < 0 || y >= N)
        return;
    if (mat[x][y] != prevV)
        return;
    // Replace the color at (x, y)
    mat[x][y] = newV;
    // Recur for north, east, south and west
    floodFillUtil(mat, x+1, y, prevV, newV);
    floodFillUtil(mat, x-1, y, prevV, newV);
    floodFillUtil(mat, x, y+1, prevV, newV);
    floodFillUtil(mat, x, y-1, prevV, newV);
}
// Returns size of maximum size subsquare matrix
// surrounded by 'X'
int replaceSurrounded(char mat[][N])
{
   // Step 1: Replace all 'O'  with '-'
   for (int i=0; i<M; i++)
      for (int j=0; j<N; j++)
          if (mat[i][j] == 'O')
             mat[i][j] = '-';
   // Call floodFill for all '-' lying on edges
   for (int i=0; i<M; i++)   // Left side
      if (mat[i][0] == '-')
        floodFillUtil(mat, i, 0, '-', 'O');
   for (int i=0; i<M; i++)  //  Right side
      if (mat[i][N-1] == '-')
        floodFillUtil(mat, i, N-1, '-', 'O');
   for (int i=0; i<N; i++)   // Top side
      if (mat[0][i] == '-')
        floodFillUtil(mat, 0, i, '-', 'O');
   for (int i=0; i<N; i++)  // Bottom side
      if (mat[M-1][i] == '-')
        floodFillUtil(mat, M-1, i, '-', 'O');
   // Step 3: Replace all '-' with 'X'
   for (int i=0; i<M; i++)
      for (int j=0; j<N; j++)
         if (mat[i][j] == '-')
             mat[i][j] = 'X';
}
// Driver program to test above function
int main()
{
    char mat[][N] =  {{'X', 'O', 'X', 'O', 'X', 'X'},
                     {'X', 'O', 'X', 'X', 'O', 'X'},
                     {'X', 'X', 'X', 'O', 'X', 'X'},
                     {'O', 'X', 'X', 'X', 'X', 'X'},
                     {'X', 'X', 'X', 'O', 'X', 'O'},
                     {'O', 'O', 'X', 'O', 'O', 'O'},
                    };
    replaceSurrounded(mat);
    for (int i=0; i<M; i++)
    {
      for (int j=0; j<N; j++)
          cout << mat[i][j] << " ";
      cout << endl;
    }
    return 0;
}

Output:

X O X O X X
X O X X X X
X X X X X X
O X X X X X
X X X O X O
O O X O O O

Time Complexity of the above solution is O(MN). Note that every element of matrix is processed at most three times.

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

Create a matrix with alternating rectangles of O and X

Write a code which inputs two numbers m and n and creates a matrix of size m x n (m rows and n columns) in which every elements is either X or 0. The Xs and 0s must be filled alternatively, the matrix should have outermost rectangle of Xs, then a rectangle of 0s, then a rectangle of Xs, and so on.

Examples:

Input: m = 3, n = 3
Output: Following matrix
X X X
X 0 X
X X X

Input: m = 4, n = 5
Output: Following matrix
X X X X X
X 0 0 0 X
X 0 0 0 X
X X X X X

Input:  m = 5, n = 5
Output: Following matrix
X X X X X
X 0 0 0 X
X 0 X 0 X
X 0 0 0 X
X X X X X

Input:  m = 6, n = 7
Output: Following matrix
X X X X X X X
X 0 0 0 0 0 X
X 0 X X X 0 X
X 0 X X X 0 X
X 0 0 0 0 0 X
X X X X X X X

We strongly recommend to minimize the browser and try this yourself first.

This question was asked in campus recruitment of Shreepartners Gurgaon. I followed the following approach.

1) Use the code for Printing Matrix in Spiral form.
2) Instead of printing the array, inserted the element ‘X’ or ‘0’ alternatively in the array.

Following is C implementation of the above approach.

#include <stdio.h>
// Function to print alternating rectangles of 0 and X
void fill0X(int m, int n)
{
    /*  k - starting row index
        m - ending row index
        l - starting column index
        n - ending column index
        i - iterator    */
    int i, k = 0, l = 0;
    // Store given number of rows and columns for later use
    int r = m, c = n;
    // A 2D array to store the output to be printed
    char a[m][n];
    char x = 'X'; // Iniitialize the character to be stoed in a[][]
    // Fill characters in a[][] in spiral form. Every iteration fills
    // one rectangle of either Xs or Os
    while (k < m && l < n)
    {
        /* Fill the first row from the remaining rows */
        for (i = l; i < n; ++i)
            a[k][i] = x;
        k++;
        /* Fill the last column from the remaining columns */
        for (i = k; i < m; ++i)
            a[i][n-1] = x;
        n--;
        /* Fill the last row from the remaining rows */
        if (k < m)
        {
            for (i = n-1; i >= l; --i)
                a[m-1][i] = x;
            m--;
        }
        /* Print the first column from the remaining columns */
        if (l < n)
        {
            for (i = m-1; i >= k; --i)
                a[i][l] = x;
            l++;
        }
        // Flip character for next iteration
        x = (x == '0')? 'X': '0';
    }
    // Print the filled matrix
    for (i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
            printf("%c ", a[i][j]);
        printf("\n");
    }
}
/* Driver program to test above functions */
int main()
{
    puts("Output for m = 5, n = 6");
    fill0X(5, 6);
    puts("\nOutput for m = 4, n = 4");
    fill0X(4, 4);
    puts("\nOutput for m = 3, n = 4");
    fill0X(3, 4);
    return 0;
}

Output:

Output for m = 5, n = 6
X X X X X X
X 0 0 0 0 X
X 0 X X 0 X
X 0 0 0 0 X
X X X X X X

Output for m = 4, n = 4
X X X X
X 0 0 X
X 0 0 X
X X X X

Output for m = 3, n = 4
X X X X
X 0 0 X
X X X X

Time Complexity: O(mn)
Auxiliary Space: O(mn)

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

Find sum of all elements in a matrix except the elements in row and/or column of given cell?

Given a 2D matrix and a set of cell indexes e.g., an array of (i, j) where i indicates row and j column. For every given cell index (i, j), find sums of all matrix elements except the elements present in i’th row and/or j’th column.

Example:
mat[][]  = { {1, 1, 2}
             {3, 4, 6}
             {5, 3, 2} }
Array of Cell Indexes: {(0, 0), (1, 1), (0, 1)}
Output:  15, 10, 16

A Naive Solution is to one by once consider all given cell indexes. For every cell index (i, j), find the sum of matrix elements that are not present either at i’th row or at j’th column. Below is C++ implementation of the Naive approach.

#include<bits/stdc++.h>
#define R 3
#define C 3
using namespace std;
// A structure to represent a cell index
struct Cell
{
    int r; // r is row, varies from 0 to R-1
    int c; // c is column, varies from 0 to C-1
};
// A simple solution to find sums for a given array of cell indexes
void printSums(int mat[][C], struct Cell arr[], int n)
{
    // Iterate through all cell indexes
    for (int i=0; i<n; i++)
    {
        int sum = 0, r = arr[i].r, c = arr[i].c;
        // Compute sum for current cell index
        for (int j=0; j<R; j++)
            for (int k=0; k<C; k++)
                if (j != r && k != c)
                    sum += mat[j][k];
        cout << sum << endl;
    }
}
// Driver program to test above
int main()
{
    int mat[][C] = {{1, 1, 2}, {3, 4, 6}, {5, 3, 2}};
    struct Cell arr[] = {{0, 0}, {1, 1}, {0, 1}};
    int n = sizeof(arr)/sizeof(arr[0]);
    printSums(mat, arr, n);
    return 0;
}

Output:

15
10
16

Time complexity of the above solution is O(n * R * C) where n is number of given cell indexes and R x C is matrix size.

An Efficient Solution can compute all sums in O(R x C + n) time. The idea is to precompute total sum, row and column sums before processing the given array of indexes. Below are details
1. Calculate sum of matrix, call it sum.
2. Calculate sum of individual rows and columns. (row[] and col[])
3. For a cell index (i, j), the desired sum will be “sum- row[i] – col[j] + arr[i][j]”

Below is C++ implementation of above idea.

// An efficient C++ program to compute sum for given array of cell indexes
#include<bits/stdc++.h>
#define R 3
#define C 3
using namespace std;
// A structure to represent a cell index
struct Cell
{
    int r; // r is row, varies from 0 to R-1
    int c; // c is column, varies from 0 to C-1
};
void printSums(int mat[][C], struct Cell arr[], int n)
{
    int sum = 0;
    int row[R] = {};
    int col[C] = {};
    // Compute sum of all elements, sum of every row and sum every column
    for (int i=0; i<R; i++)
    {
      for (int j=0; j<C; j++)
       {
             sum += mat[i][j];
             col[j] += mat[i][j];
             row[i] += mat[i][j];
       }
    }
    // Compute the desired sum for all given cell indexes
    for (int i=0; i<n; i++)
    {
        int ro = arr[i].r, co = arr[i].c;
        cout << sum - row[ro] - col[co] + mat[ro][co] << endl;
    }
}
// Driver program to test above function
int main()
{
    int mat[][C] = {{1, 1, 2}, {3, 4, 6}, {5, 3, 2}};
    struct Cell arr[] = {{0, 0}, {1, 1}, {0, 1}};
    int n = sizeof(arr)/sizeof(arr[0]);
    printSums(mat, arr, n);
    return 0;
}

Output:

15
10
16

Time Complexity: O(R x C + n)
Auxiliary Space: O(R + C)

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

Rotate Matrix Elements

Given a matrix, clockwise rotate elements in it.

Examples:

Input
1    2    3
4    5    6
7    8    9

Output:
4    1    2
7    5    3
8    9    6

For 4*4 matrix
Input:
1    2    3    4
5    6    7    8
9    10   11   12
13   14   15   16

Output:
5    1    2    3
9    10   6    4
13   11   7    8
14   15   16   12

The idea is to use loops similar to the program for printing a matrix in spiral form. One by one rotate all rings of elements, starting from the outermost. To rotate a ring, we need to do following.
1) Move elements of top row.
2) Move elements of last column.
3) Move elements of bottom row.
4) Move elements of first column.
Repeat above steps for inner ring while there is an inner ring.

// C++ program to rotate a matrix
#include <bits/stdc++.h>
#define R 4
#define C 4
using namespace std;
// A function to rotate a matrix mat[][] of size R x C.
// Initially, m = R and n = C
void rotatematrix(int m, int n, int mat[R][C])
{
    int row = 0, col = 0;
    int prev, curr;
    /*
       row - Staring row index
       m - ending row index
       col - starting column index
       n - ending column index
       i - iterator
    */
    while (row < m && col < n)
    {
        if (row + 1 == m || col + 1 == n)
            break;
        // Store the first element of next row, this
        // element will replace first element of current
        // row
        prev = mat[row + 1][col];
         /* Move elements of first row from the remaining rows */
        for (int i = col; i < n; i++)
        {
            curr = mat[row][i];
            mat[row][i] = prev;
            prev = curr;
        }
        row++;
        /* Move elements of last column from the remaining columns */
        for (int i = row; i < m; i++)
        {
            curr = mat[i][n-1];
            mat[i][n-1] = prev;
            prev = curr;
        }
        n--;
         /* Move elements of last row from the remaining rows */
        if (row < m)
        {
            for (int i = n-1; i >= col; i--)
            {
                curr = mat[m-1][i];
                mat[m-1][i] = prev;
                prev = curr;
            }
        }
        m--;
        /* Move elements of first column from the remaining rows */
        if (col < n)
        {
            for (int i = m-1; i >= row; i--)
            {
                curr = mat[i][col];
                mat[i][col] = prev;
                prev = curr;
            }
        }
        col++;
    }
    // Print rotated matrix
    for (int i=0; i<R; i++)
    {
        for (int j=0; j<C; j++)
          cout << mat[i][j] << " ";
        cout << endl;
    }
}
/* Driver program to test above functions */
int main()
{
    // Test Case 1
    int a[R][C] = { {1,  2,  3,  4},
        {5,  6,  7,  8},
        {9,  10, 11, 12},
        {13, 14, 15, 16}  };
    // Tese Case 2
    /* int a[R][C] = {{1, 2, 3},
                      {4, 5, 6},
                      {7, 8, 9}
                     };
     */  rotatematrix(R, C, a);
    return 0;
}

Output:

5 1 2 3
9 10 6 4
13 11 7 8
14 15 16 12

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

Amazon Interview Experience | Set 221

I gave my round 1 amazon. There were two coding questions.

1) Given an integer n in the input, find its next sparse binary numberA sparse binary number is a number whose binary representation does not contain any consecutive 1s.

For eg.
72 is a sparse binary number, because its binary representation (01001000) does not contain any consecutive 1s.
17 is a sparse binary number, because its binary representation (00010001) does not contain any consecutive 1s.

Similarly,
12 is a non sparse binary number, because its binary representation (00001100) contains consecutive 1s.
43 is a non sparse binary number, because its binary representation (00101011) contains consecutive 1s.

Now, given an integer n in the input, find its next sparse binary number. n itself can be sparse or non sparse.

where n >= 0 and n < 2^31 Input 12 Output 16 Explanation 12 is 00001100 and next sparse no. to it is 16 (00010000). 2) You are given heights of n candles. First day you lit one candle s Scond day you need to lit two candles Third day you need to lit three candles ………. …….. till possible. After lighting candles the height of candles deduced by 1 each day.You can also extinguish any candle you want but only at the end of day. So you need to tell the maximum number number of days , you can carry on lighting the candles. Example : there are three candles of heights {2 , 2 ,2 } Answer : 3 1.You light first candle on day one. heights -> {1,2,2}
2.You light second and third and extinguish first one . heights ->{1, 1,1}
3.You light all the candles. heights -{0,0,0}

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

Sparse Matrix and its representations | Set 1 (Using Arrays and Linked Lists)

A matrix is a two-dimensional data object made of m rows and n columns, therefore having total m x n values. If most of the elements of the matrix have 0 value, then it is called a sparse matrix.

Why to use Sparse Matrix instead of simple matrix ?

  • Storage: There are lesser non-zero elements than zeros and thus lesser memory can be used to store only those elements.
  • Computing time: Computing time can be saved by logically designing a data structure traversing only non-zero elements..

Example:

0 0 3 0 4
0 0 5 7 0
0 0 0 0 0
0 2 6 0 0

Representing a sparse matrix by a 2D array leads to wastage of lots of memory as zeroes in the matrix are of no use in most of the cases. So, instead of storing zeroes with non-zero elements, we only store non-zero elements. This means storing non-zero elements with triples- (Row, Column, value).

Sparse Matrix Representations can be done in many ways following are two common representations:

  1. Array representation
  2. Linked list representation

Method 1: Using Arrays

2D array is used to represent a sparse matrix in which there are three rows named as

  • Row: Index of row, where non-zero element is located
  • Column: Index of column, where non-zero element is located
  • Value: Value of the non zero element located at index – (row,column)

Sparse Matrix Array Representation

// C program for Sparse Matrix Representation
// using Linked Lists
#include<stdio.h>
int main()
{
    // Assume 4x5 sparse matrix
    int sparseMatrix[4][5] =
    {
        {0 , 0 , 3 , 0 , 4 },
        {0 , 0 , 5 , 7 , 0 },
        {0 , 0 , 0 , 0 , 0 },
        {0 , 2 , 6 , 0 , 0 }
    };
    int size = 0;
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 5; j++)
            if (sparseMatrix[i][j] != 0)
                size++;
    // number of columns in compactMatrix (size) must be
    // equal to number of non - zero elements in
    // sparseMatrix
    int compactMatrix[3][size];
    // Making of new matrix
    int k
    for (i = 0; i < 4; i++)
        for (j = 0; j < 5; j++)
            if (sparseMatrix[i][j] != 0)
            {
                compactMatrix[0][k] = i;
                compactMatrix[1][k] = j;
                compactMatrix[2][k] = sparseMatrix[i][j];
                k++;
            }
    for (i=0; i<3; i++)
    {
        for (j=0; j<size; j++)
            printf("%d ", compactMatrix[i][j]);
        printf("\n");
    }
    return 0;
}

Output:

0 0 1 1 3 3
2 4 2 3 1 2
3 4 5 7 2 6

 

Method 2: Using Linked Lists

In linked list, each node has four fields. These four fields are defined as:

  • Row: Index of row, where non-zero element is located
  • Column: Index of column, where non-zero element is located
  • Value: Value of the non zero element located at index – (row,column)
  • Next node: Address of the next node

Sparse-Matrix-Linked-List 2

// C program for Sparse Matrix Representation
// using Linked Lists
#include<stdio.h>
#include<stdlib.h>
// Node to represent sparse matrix
struct Node
{
    int value;
    int row_position;
    int column_postion;
    struct Node *next;
};
// Function to create new node
void create_new_node(struct Node** start, int non_zero_element,
                     int row_index, int column_index )
{
    struct Node *temp, *r;
    temp = *start;
    if (temp == NULL)
    {
        // Create new node dynamically
        temp = (struct Node *) malloc (sizeof(struct Node));
        temp->value = non_zero_element;
        temp->row_position = row_index;
        temp->column_postion = column_index;
        temp->next = NULL;
        *start = temp;
    }
    else
    {
        while (temp->next != NULL)
            temp = temp->next;
        // Create new node dynamically
        r = (struct Node *) malloc (sizeof(struct Node));
        r->value = non_zero_element;
        r->row_position = row_index;
        r->column_postion = column_index;
        r->next = NULL;
        temp->next = r;
    }
}
// This function prints contents of linked list
// starting from start
void PrintList(struct Node* start)
{
    struct Node *temp, *r, *s;
    temp = r = s = start;
    printf("row_position: ");
    while(temp != NULL)
    {
        printf("%d ", temp->row_position);
        temp = temp->next;
    }
    printf("\n");
    printf("column_postion: ");
    while(r != NULL)
    {
        printf("%d ", r->column_postion);
        r = r->next;
    }
    printf("\n");
    printf("Value: ");
    while(s != NULL)
    {
        printf("%d ", s->value);
        s = s->next;
    }
    printf("\n");
}
// Driver of the program
int main()
{
   // Assume 4x5 sparse matrix
    int sparseMatric[4][5] =
    {
        {0 , 0 , 3 , 0 , 4 },
        {0 , 0 , 5 , 7 , 0 },
        {0 , 0 , 0 , 0 , 0 },
        {0 , 2 , 6 , 0 , 0 }
    };
    /* Start with the empty list */
    struct Node* start = NULL;
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 5; j++)
            // Pass only those values which are non - zero
            if (sparseMatric[i][j] != 0)
                create_new_node(&start, sparseMatric[i][j], i, j);
    PrintList(start);
    return 0;
}

Output:

row_position: 0 0 1 1 3 3
column_postion: 2 4 2 3 1 2
Value: 3 4 5 7 2 6



Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

Search in a row wise and column wise sorted matrix

Given an n x n matrix and a number x, find position of x in the matrix if it is present in it. Else print “Not Found”. In the given matrix, every row and column is sorted in increasing order. The designed algorithm should have linear time complexity.

Example :

Input : mat[4][4] = { {10, 20, 30, 40},
                      {15, 25, 35, 45},
                      {27, 29, 37, 48},
                      {32, 33, 39, 50}};
              x = 29
Output : Found at (2, 1)

Input : mat[4][4] = { {10, 20, 30, 40},
                      {15, 25, 35, 45},
                      {27, 29, 37, 48},
                      {32, 33, 39, 50}};
              x = 100
Output : Element not found

A simple solution is to search one by one. Time complexity of this solution is O(n2).

A better solution is to use Divide and Conquer to find the element. Time complexity of this solution is O(n1.58).

Below is an efficient solution that works in O(n) time.
1) Start with top right element
2) Loop: compare this element e with x
….i) if they are equal then return its position
…ii) e < x then move it to down (if out of bound of matrix then break return false) ..iii) e > x then move it to left (if out of bound of matrix then break return false)
3) repeat the i), ii) and iii) till you find element or returned false

Thanks to devendraiiit for suggesting below approach.

Implementation:

// C program to search an element in row-wise
// and column-wise sorted matrix
#include<stdio.h>
/* Searches the element x in mat[][]. If the
   element is found, then prints its position
   and returns true, otherwise prints "not found"
   and returns false */
int search(int mat[4][4], int n, int x)
{
   int i = 0, j = n-1;  //set indexes for top right element
   while ( i < n && j >= 0 )
   {
      if ( mat[i][j] == x )
      {
         printf("n Found at %d, %d", i, j);
         return 1;
      }
      if ( mat[i][j] > x )
        j--;
      else //  if mat[i][j] < x
        i++;
   }
   printf("n Element not found");
   return 0;  // if ( i==n || j== -1 )
}
// driver program to test above function
int main()
{
  int mat[4][4] = { {10, 20, 30, 40},
                    {15, 25, 35, 45},
                    {27, 29, 37, 48},
                    {32, 33, 39, 50},
                  };
  search(mat, 4, 29);
  return 0;
}

Output :

n Found at 2, 1

Time Complexity: O(n)

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

Convert Big Endian to Little Endian?

Both of technique is used to store bits in memory address.

Big Endian:-  the most significant byte is stored in  the smallest address

Little Endian:- the least significant bytes are stored in the largest address

Example to store 1234 number

Big Endian                                                                         Little Endian

Address          Number                                            Address        Number

1000                   1                                                   1000                4

2000                    2                                                   2000                3

3000                    3                                                   3000                2

4000                    4                                                  4000                  1

PROGRAM

#include <stdio.h>

/* function to show bytes in memory, from location start to start+n*/
void show_mem_rep(char *start, int n)
{
int i;
for (i = 0; i < n; i++)
printf(” %.2x”, start[i]);
printf(“\n”);
}

/*Main function to call above function for 0x01234567*/
int main()
{
int i = 0x01234567;
show_mem_rep((char *)&i, sizeof(i));
getchar();
return 0;
}

.above program for little endian : 67 45 23 01

big endian : 01 23 45 67

Minimum Spanning Tree (Function Program)

Given a weighted, undirected and connected graph. The task is to find the sum of weights of  the edges of the Minimum Spanning Tree. You need to complete the function spanningTree which takes a graph g as its argument and returns an integer denoting the sum of weights of the edges of the Minimum Spanning Tree.

Input:
The first line of input contains an integer T denoting the no of test cases . Then T test cases follow. The first line of each test case contains two integers n,e denoting the no of nodes and no of edges. Then in the next line are E*3 space separated values a b w where a,b denotes an edge from a to b and w is the weight of the edge.

Output:
For each test case in a new line print the sum of weights of  the edges of the Minimum Spanning Tree formed of the graph.

Constraints:
1<=T<=10
1<=n,e<=100
1<=w<=1000

Example(To be used only for expected output):
Input

2
3 3
1 2 5 2 3 3 1 3 1
2 1
1 2 5
Output
4
5

Note:The Input/Ouput format and Example given are used for system’s internal purpose, and should be used by a user for Expected Output only. As it is a function problem, hence a user should not read any input from stdin/console. The task is to complete the function specified, and not to write the full code.

**For More Examples Use Expected Output**

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

Implementing Dijkstra | Set 1 (Adjacency Matrix) (Function Program)

Given an adjacency matrix (graph), the task is to find the shortest distance of all the vertex’s from the source vertex. You are required to complete the function dijkstra which takes 3 arguments. The first argument is the adjacency matrix (graph) , the second argument is the source vertex s and the third argument is V denoting the size of the matrix. The function prints  V space separated integers where i’th integer denotes the shortest distance of the i’th vertex from source vertex.

Input:
The first line of input contains an integer T denoting the no of test cases . Then T test cases follow .The first line of each test case contains an integer V denoting the size of the adjacency matrix  and in the next line are V space separated values of the matrix (graph) .The third line of each test case contains an integer denoting the source vertex s.

Output:
For each test case output will be V space separated integers where the ith integer denote the shortest distance of ith vertex from source vertex.

Constraints:
1<=T<=20
1<=V<=20
0<=s 1<=graph[][]<=1000

Example:
Input
2
2
0 25 25 0
0
3
0 1 43 1 0 6 43 6 0
2

Output
0 25
7 6 0

 

**For More Examples Use Expected Output**

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org