public class Nqueen {
private final int dim = 8;
private final int queen = 1;
private int[][] chessBoard = new int[dim][dim];
private int count = 0;
private int startrow = 0;
public void initialize()
{
setUpBoard();
solve(0);
System.out.println("\n\nTOTAL NO. OF SOLUTIONS : " + count);
}
/*
* This function checks whether a queen can be place in cell marked by (row,col)
* If yes then returns true
* Else returns false
*/
public boolean isSafe(int row, int col)
{
for(int i=0; i<dim ; i++)
{
if(chessBoard[i][col] == queen && i!= row)
return false;
if(chessBoard[row][i] == queen && i != col)
return false;
}
//diagnol check
int i = row-1 , j= col-1;
while(i>=0 && j>=0)
{
if(chessBoard[i][j] == queen)
return false;
i--;
j--;
}
i = row+1;
j=col+1;
while(i<dim && j<dim)
{
if(chessBoard[i][j] == queen)
return false;
i++;
j++;
}
i= row-1;
j = col+1;
while(i>=0 && j<dim)
{
if(chessBoard[i][j] == queen)
return false;
i--;
j++;
}
i = row+1;
j = col-1;
while(i<dim && j>=0)
{
if(chessBoard[i][j] == queen)
return false;
i++;
j--;
}
return true;
}
/*
* This function initialized board to all 0's
*/
public void setUpBoard()
{
for(int i=0; i<dim ; i++)
{
for(int j=0; j<dim ; j++)
{
chessBoard[i][j] = 0;
}
}
}
/*
* This function place a queen at row, col position
*/
public void placeQueen(int row, int col)
{
chessBoard[row][col] = queen;
}
/*
* This function removes a queen placed at row, col position
*/
public void removeQueen(int row, int col)
{
chessBoard[row][col] = 0;
}
/*
* This function displays the chess board.
*/
public void displayChessBoard()
{
for(int i=0 ; i< dim ; i++)
{
System.out.println();
for(int j=0 ; j<dim ; j++)
{
System.out.print(chessBoard[i][j] + " ");
}
}
}
/*
* This function uses backtracking approach and check all possible test cases.
*/
public void solve(int col)
{
if(col >= dim)
{
count++;
System.out.println();
displayChessBoard();
return;
}
for(int row =startrow ; row<dim ; row++)
{
if(isSafe(row,col))
{
placeQueen(row,col);
solve(col+1);
removeQueen(row,col);
}
}
}
public static void main(String args[])
{
Nqueen n = new Nqueen();
n.initialize();
}
}
Monday 20 August 2012
N QUEEN PROBLEM: On a NxN board place N queens such that no queen is under attack where a queen can move any steps horizontally, vertically and diagnolly.
Sunday 12 August 2012
Given an array containing only 0's and 1's, now we have to find the maximum subarray which contain equal no of 0's and 1's. Time complexity O(n).
/*
Logic for this program is taken from a post on geeksforgeeks.
I couldn't deduce an O(n) logic.
*/
Logic for this program is taken from a post on geeksforgeeks.
I couldn't deduce an O(n) logic.
*/
#include<conio.h>
#include<iostream.h>
void main()
{
clrscr();
int array[]={1,0,0,1,0,1,1};
int len = sizeof(array)/sizeof(int);
int *sum = new int[len];
sum[0]=((array[0]==0)?-1:1);
int min=array[0],max=array[0];
for(int i=1;i<len;i++)
{
sum[i]=sum[i-1]+((array[i]==0)?-1:1);
if(sum[i]>max)
max=sum[i];
if(sum[i]<min)
min=sum[i];
}
int *hash = new [max-min+1];
int maxsize =-1,startindex;
for( i=0;i<max-min+1;i++)
hash[i]=-1;
for(i=0;i<len;i++)
{
if(sum[i]==0)
{
maxsize=i+1;
startindex=0;
}
if(hash[sum[i]-min]==-1)
hash[sum[i]-min]=i;
else
{
if((i-hash[sum[i]-min]) >
maxsize)
{
maxsize=i-hash[sum[i]-min];
startindex =
hash[sum[i]-min];
}
}
}
cout<<"\n START :
"<<startindex;
cout<<"\n END : "<<maxsize+startindex-1;
getch();
}
Wednesday 8 August 2012
Without using extra space place all zeroes to left and 1's to right from an array of Zero's and 1's as below 011001 ans. 000111
#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();
int a[]={0,1,1,0,0,1};
int n=sizeof(a)/sizeof(int);
int i=0,j=n-1;
while(i<j)
{
if(a[i]==0)
i++;
if(a[j]==1)
j--;
if(a[i]==1 && a[j]==0)
{
a[i]=0;
a[j]=1;
i++;
j--;
}
}
for(i=0;i<n;i++)
cout<<"
"<<a[i];
getch();
}
Find the subset of an array having maximum sum
#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();
int a[]={1,3,-8,2,-1,10,-2,1};
int n=sizeof(a)/sizeof(int);
int sum=a[0];
int max=-1;
int start,end,s=0,e=0;
for(int i=1;i<n;i++)
{
if(sum>=max)
{
start=s;
end=e;
max=sum;
}
if(sum<0)
{
s=e=i;
sum=a[i];
continue;
}
sum+=a[i];
e=i;
}
cout<<max;
getch();
}
There is an integer array consisting positive and negative integers. Find maximum positive difference S defined as: S = a[i] - a[j] where i>j and S > 0
#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();
int arr[] ={-3,5,2,-2,1,0,-6,7,-8,2};
int n=10,min=arr[0],max=-32767 ;
for(int i=1;i<n;i++)
{
if(arr[i]<min)
{
min=arr[i];
continue;
}
if(arr[i]-min>max)
max=arr[i]-min;
}
cout<<"MAX DIFFERENCE IS :
"<<max;
getch();
}
Find 3 numbers in the given array such that their sum is equal to a given number.
#include<iostream.h>
#include<conio.h>
int
array[]={10,20,30,40,50,60,70,80,90};
int n=9;
int check(int
k,int val)
{
int i=0,j=n-1;
static int flag;
while(i<j)
{
if(i==k)
{
i++;
continue;
}
if(j==k)
{
j--;
continue;
}
if(array[i]+array[j]==val)
{
cout<<"\n"<<array[i]<<"
+ "<<array[j]<<" + "<<array[k]<<" =
"<<val+array[k];
flag++;
i++;
j--;
}
else if(array[i]+array[j]>val)
j--;
else
i++;
}
return flag;
}
void main()
{
clrscr();
int val,flag;
cout<<"Enter the value ";
cin>>val;
cout<<" \n\n";
for(int i=0;i<n;i++)
flag=check(i,val-array[i]);
if(flag==0)
cout<<"\n No such
elements ";
getch();
}
Inorder and Preorder tree traversal without recursion.
#include<iostream.h>
#include<process.h>
#include<math.h>
#include<conio.h>
class node
{
public:
node *left;
node *right;
int data;
node()
{
left=NULL;
right=NULL;
}
}*root=NULL;
int flag=0;
void add(node
*parent,node *r,int d,int level,int item)
{
if(r!=NULL)
{
add(r,r->left,d+1,level,item);
add(r,r->right,d+1,level,item);
}
else if(d==level && flag!=1)
{
flag=1;
node *newnode = new node;
newnode->data=item;
if(parent->left==NULL)
parent->left=newnode;
else
parent->right=newnode;
}
}
void npreorder()
{
node *ptr=root;
int top=-1;
node **stack = new node*[50];
while(1)
{
if(ptr!=NULL)
{
cout<<" "<<ptr->data;
if(ptr->right!=NULL)
stack[++top]=ptr->right;
ptr=ptr->left;
}
else
{
ptr=stack[top--];
if(top==-2)
return;
}
}
}
void ninorder()
{
node **stack= new node*[50];
int top=0;
node *ptr=root,*process=NULL;
while(top>=0)
{
if(ptr && process!=ptr)
{
stack[++top]=ptr;
ptr=ptr->left;
}
else
{
ptr=stack[top--];
process=ptr;
cout<<" "<<ptr->data;
if(ptr->right)
ptr=ptr->right;
}
}
}
void main()
{
clrscr();
int ch,item;
cout<<"1.ADD\n2.PREORDER\n3.DEPTH\n4.NO
OF ELEMENTS\n5.TRACE";
cout<<"\n6.BFS AND
DFS\n7.EXIt";
while(1)
{
cout<<"\nchoice? ";
cin>>ch;
switch(ch)
{
case 1: cout<<"ITEM
:";
cin>>item;
flag=0;
if(root==NULL)
{
node *newnode =
new node;
newnode->data=item;
root=newnode;
}
else
{
maxdepth=0;
depth(root,0);
int level;
int
elements=count(root);
if(elements==(pow(2,maxdepth+1)-1))
level=maxdepth+1;
else
level=maxdepth;
add(root,root,0,level,item);
}
break;
case 2: ninorder();
//npreorder();
//preorder(root);
break;
case 3: maxdepth=0;
depth(root,0);
cout<<maxdepth;
break;
case 4:
cout<<count(root);
break;
case 5: equal=0;
cout<<"ITEM
TO TRACE : ";
cin>>item;
trace(root,item);
break;
case 6:
cout<<"\nBFS\n";
bfs();
cout<<"\nDFS\n";
dfs();
break;
case 7: exit(0);
}
}
}
Count the number of elements in a binary tree.
int count(node
*r)
{
if(r==NULL)
return 0;
else
{
int c=1;
c+=count(r->left);
c+=count(r->right);
return c;
}
}
calculate the depth of the binary tree.
int maxdepth=0;
void depth(node
*r,int d)
{
if(r!=NULL)
{
if(maxdepth<d)
maxdepth=d;
depth(r->left,d+1);
depth(r->right,d+1);
}
}In a binary tree given any node, trace its path from root node.
//set equal=0 before calling trace function.
int equal=0;
void trace(node
*r,int item)
{
if(equal==1)
return;
if(r->data==item)
equal=1;
if(r!=NULL)
{
trace(r->left,item);
trace(r->right,item);
if(equal==1)
cout<<" "<<r->data;
}
}Print bfs and dfs traversal of binary tree.
void bfs()
{
if(root==NULL)
{
cout<<"\nEMPTY
LIST";
return;
}
node **queue = new node*[count(root)];
int front=0;
int rear=0;
queue[front]=root;
node *pnode;
while(front<=rear)
{
pnode=queue[front++];
cout<<" "<<pnode->data;
if(pnode->left!=NULL)
queue[++rear]=pnode->left;
if(pnode->right!=NULL)
queue[++rear]=pnode->right;
}
}
void dfs()
{
if(root==NULL)
{
cout<<"\nEMPTY
LIST";
return;
}
node **stack = new node*[count(root)];
int top=0;
stack[top]=root;
node *pnode;
while(top>=0)
{
pnode=stack[top--];
cout<<" "<<pnode->data;
if(pnode->left!=NULL)
stack[++top]=pnode->left;
if(pnode->right!=NULL)
stack[++top]=pnode->right;
}
}
Monday 6 August 2012
In a linked list print odd nodes first and then even nodes and also sort a linked list
#include<iostream.h>
#include<process.h>
#include<conio.h>
class node
{
public:
node *next;
int data;
node()
{
next=NULL;
}
}*start=NULL;
void display()
{
if(start==NULL)
{
cout<<"empty list";
return;
}
node *ptr=start;
while(ptr!=NULL)
{
cout<<" "<<ptr->data;
ptr=ptr->next;
}
}
void insert(int
item)
{
node *newnode = new node;
newnode->data=item;
if(start==NULL)
{
start=newnode;
return;
}
node *ptr=start;
while(ptr->next!=NULL)
ptr=ptr->next;
ptr->next=newnode;
}
void del(int
item)
{
if(start->data==item)
{
start=start->next;
return;
}
node *pre=NULL,*ptr=start;
while(ptr!=NULL)
{
if(ptr->data==item)
{
pre->next=ptr->next;
return;
}
pre=ptr;
ptr=ptr->next;
}
cout<<"ITEM NOT IN LIST";
}
void sort()
{
node *min,*parmin;
for(node
*ptr1=start,*parptr1=NULL;ptr1->next!=NULL;)
{
min=ptr1;
for(node
*ptr2=ptr1->next,*save=ptr1;ptr2!=NULL;)
{
if(ptr2->data<min->data)
{
min=ptr2;
parmin=save;
}
save=ptr2;
ptr2=ptr2->next;
}
if(min!=ptr1)
{
parmin->next=min->next;
min->next=ptr1;
if(parptr1==NULL)
{
start=min;
parptr1=min;
}
else
{
parptr1->next=min;
parptr1=min;
}
}
else
{
parptr1=ptr1;
ptr1=ptr1->next;
}
}
}
void main()
{
clrscr();
cout<<"1.INSERT\n2.DELETE\n3.DISPLAY\n4.ALL
ODD FIRST\n";
cout<<"5.SORT\n6.REVERSE\n7.ALTERNATE
REVERSE\n8.Nth ELEMENT FROM LAST\n9.Exit\n";
int ch,item;
while(1)
{
cout<<"\nchoice? ";
cin>>ch;
switch(ch)
{
case 1: cout<<"ITEM TO INSERT";
cin>>item;
insert(item);
break;
case 2: cout<<"ITEM TO DELETE";
cin>>item;
del(item);
break;
case 3: display();
break;
case 4:// sort();
evenodd();
display();
break;
case 5: sort();
display();
break;
case 6: //node
*ptr=reverse(start);
// ptr->next=NULL;
i_reverse();
break;
case 7: kreverse(4);
//altreverse();
break;
case 8: int n;
cout<<" ENTER
N ";
cin>>n;
fromlast(n);
break;
case 9: exit(0);
}
}
}
Subscribe to:
Posts (Atom)