Aditya Goel
BAN USER// A C++ program to find the largest subsquare
// surrounded by 'X' in a given matrix of 'O' and 'X'
#include<iostream>
using namespace std;
// Size of given matrix is N X N
#define N 6
// A utility function to find minimum of two numbers
int getMin(int x, int y) { return (x<y)? x: y; }
// Returns size of maximum size subsquare matrix
// surrounded by 'X'
int findSubSquare(int mat[][N])
{
int max = 1; // Initialize result
// Initialize the left-top value in hor[][] and ver[][]
int hor[N][N], ver[N][N];
hor[0][0] = ver[0][0] = (mat[0][0] == 'X');
// Fill values in hor[][] and ver[][]
for (int i=0; i<N; i++)
{
for (int j=0; j<N; j++)
{
if (mat[i][j] == 'O')
ver[i][j] = hor[i][j] = 0;
else
{
hor[i][j] = (j==0)? 1: hor[i][j-1] + 1;
ver[i][j] = (i==0)? 1: ver[i-1][j] + 1;
}
}
}
// Start from the rightmost-bottommost corner element and find
// the largest ssubsquare with the help of hor[][] and ver[][]
for (int i = N-1; i>=1; i--)
{
for (int j = N-1; j>=1; j--)
{
// Find smaller of values in hor[][] and ver[][]
// A Square can only be made by taking smaller
// value
int small = getMin(hor[i][j], ver[i][j]);
// At this point, we are sure that there is a right
// vertical line and bottom horizontal line of length
// at least 'small'.
// We found a bigger square if following conditions are met:
// 1)If side of square is greater than max.
// 2)There is a left vertical line of length >= 'small'
// 3)There is a top horizontal line of length >= 'small'
if (small > max && ver[i][j-small+1] >= small && hor[i-small+1][j] >= small)
max = small;
}
}
return max;
}
// Driver program to test above function
int main()
{
int mat[][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'},
};
cout << findSubSquare(mat);
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define R 4
#define C 5
void spiralPrint(int m, int n, int a[R][C])
{
int i, k = 0, l = 0;
/* k - starting row index
m - ending row index
l - starting column index
n - ending column index
i - iterator
*/
stack<int> stk;
while (k <= m && l <= n)
{
/* Print the first row from the remaining rows */
for (i = l; i <= n; ++i)
stk.push(a[k][i]);
k++;
/* Print the last column from the remaining columns */
for (i = k; i <= m; ++i)
stk.push(a[i][n]);
n--;
/* Print the last row from the remaining rows */
if ( k <= m)
{
for (i = n; i >= l; --i)
stk.push(a[m][i]);
m--;
}
/* Print the first column from the remaining columns */
if (l <= n)
{
for (i = m; i >= k; --i)
stk.push(a[i][l]);
l++;
}
}
while(!stk.empty())
{
cout << stk.top() << " ";
stk.pop();
}
}
/* Driver program to test above functions */
int main()
{
int mat[R][C] =
{
{1, 2, 3, 4, 5},
{6, 7, 8, 9, 10},
{11, 12, 13, 14, 15},
{16, 17, 18, 19, 20}
};
spiralPrint(R - 1, C - 1, mat);
return 0;
}
int findLength(int arr[], int n)
{
int max_len = 1; // Initialize result
for (int i=0; i<n-1; i++)
{
// Initialize min and max for all subarrays starting with i
int mn = arr[i], mx = arr[i];
// Consider all subarrays starting with i and ending with j
for (int j=i+1; j<n; j++)
{
// Update min and max in this subarray if needed
mn = min(mn, arr[j]);
mx = max(mx, arr[j]);
// If current subarray has all contiguous elements
if ((mx - mn) == j-i)
max_len = max(max_len, mx-mn+1);
}
}
return max_len;
}
compiler will not report an error and their is no ambiguity...the expression b=a+++a will always evaluates to b=(a++)+a as postfix operator++ have higher precedence than prefix operator++
- Aditya Goel August 23, 2012Simplest Soln. is doing a Breadth-first search. Start with BFS on first user in which the minimum degree of connection between two users is the level no. of second user.
- Aditya Goel August 23, 2012we r allowed to traverse the array only once. it means time complexity is O(n).
no way we will use a complicated algo like "in order" merge sort to solve this problem which takes O(nlogn) time.
it shud be
else if (data[i] == 'B')
instead of
else if (data[i] == 'G')
@sushmita: it works for all value of k and n..
@Subhransu: no it is nt possible to obtain order less than n, as we hv to scan the list atleast once in order to find kth element from the end. If we know the no. of nodes n in linked list in advance, only then it is possbl to obtain order less than n
try it on input
int a[]={1,2,3,4,5,6,7,8,9};
it is giving unexpected result
1 2 7 4 5 6 3 8 9
please clarify the ques..
- Aditya Goel July 28, 2012struct list{
int data;
struct list*next;
}*start;
struct list* IterativeReverse(int k)
{
struct list*cur=NULL, *ptr1=NULL, *ptr2=NULL;
cur=start;
if(start->next)
ptr1=cur->next;
else //if linked list contains only one node.
return start;
ptr2=ptr1->next;//can be NULL in the beginning itself.
struct list*temp=cur;
k=k-1;
while(--k)//loop shud iterate <=k-2 times
{
ptr1->next=cur;
cur=ptr1;
ptr1=ptr2;
ptr2=ptr2->next;
if(!ptr2) break; //if k exceeds its no of nodes.
}
ptr1->next=cur;
temp->next=ptr2;
start=ptr1;
return ptr1;
}
call the function IterativeReverse as
start=IterativeReverse(k);
- Aditya Goel July 27, 2016