Sunday, April 15, 2012

Program 26TH in C++

PROBLEM STATEMENT :

Write a function isValid(int sudoko[][]) to chec whether a given sudoko solution is valid or not.

SOLUTION :

#include <cstdio>
#include <iostream.h>

using namespace std;

//initializing the count array with val.

void reinit(int c[9],int val)
{
for(int i=0; i<9; i++)
{
c[i]=val;
}
}

//checking whether all calues in count array are set to zero or not

bool check (int c[9])
{
for(int i=0; i<9; i++)
{
if(c[i] != 0)
{
return false;
}
}
return true;
}

//function isValid

bool isValid(int a[][9])
{
int i=0;
int j=0;
int k=0;
int p=0;
int count[]={1,1,1,1,1,1,1,1,1};

//checking first 9 blocks for validity

while(k < 9)
{
for(i=k; i<(k+3); i++)
{
for(j=p; j<(p+3); j++)
{
if(a[i][j] > 0 && a[i][j] <10)
{
count[a[i][j]-1]--;

if(count[a[i][j]-1] < 0)
{
return false;
}
}
else
{
return false;
}
}
}
if(check(count))
{
reinit(count,1);
}
else
{

return false;
}

p=p+3;
if(p == 9)
{
p=0;
k=k+3;
}

}
reinit(count,1);
//checking rows for validity

for(i=0; i<9; i++)
{
for(j=0; j<9; j++)
{
if(a[i][j] > 0 && a[i][j] < 10)
{
count[a[i][j]-1]--;
if(count[a[i][j]-1] < 0)
{
return false;
}
}
else
{
return false;
}

if(j == 8 && i!=8)
{
if(check(count))
{
reinit(count,1);
}
else
{
return false;
}
}

}
}
if(check(count))
{
reinit(count,1);
}
else
{
return false;
}

//checking columns for validity

for(j=0 ; j<9 ; j++)
{
for(i=0; i<9; i++)
{
if(a[i][j] > 0 && a[i][j] < 10)
{
count[a[i][j]-1]--;

if(count[a[i][j]-1] < 0)
{
return false;
}
}
else
{
return false;
}
if(i == 8 && j != 8)
{
if(check(count))
{
reinit(count,1);
}
}

}
}

if(check(count))
{
return true;
}
else
{
return false;
}



}

int main()
{

int a[9][9]={{2,4,8,3,9,5,7,1,6},{5,7,1,6,2,8,3,4,9},{9,3,6,7,4,1,5,8,2},{6,8,2,5,3,9,1,7,4},{3,5,9,1,7,4,6,2,8},{7,1,4,8,6,2,9,5,3},{8,6,3,4,1,7,2,9,5},{1,9,5,2,8,6,4,3,7},{4,2,7,9,5,3,8,6,1}};

if(isValid(a))
{
cout<<"true";
}
else
{
cout<<"false";
}
}

Posted by at No comments:

Program 25TH in C++


PROBLEM STATEMENT :

If you are given an input array of chars 1 2 3 4 a b c d
output should be 1 a 2 b 3 c 4 d
No Buffers should be used
variables are permissible.

SOLUTION :

#include <iostream.h>
#include <cstdio>

int main()
{

char a1[8]={'1','2','3','4','a','b','c','d'};

int strlen=sizeof(a1)/sizeof(char);
int i=0;
int j=0;

for(i=0; i<strlen; i++)
{

if(a1[i]<48 || a1[i]>57)
{
j=i;
break;
}

}


for(i=1; j<strlen; i+=2)
{

int k=j++;
char temp = a1[k];
while(k > i)
{
a1[k]=a1[k-1];
k--;

}
a1[k]=temp;
}


cout<<"\n\no/p : ";
for(i=0; i<strlen; i++)
{
cout<<a[i]<<" ";
}

}


Posted by at No comments:

Program 24TH in C++


PROBLEM STATEMENT :

Find number in a circularly sorted array.

SOLUTION :

#include <iostream.h>
#include <cstdio>

using namespace std;

int main()
{
int target;
int a1[]={6,7,8,9,1,2,3};
int a[]={3,1,9,8,7,6,5};
cout<<"\n\nEnter number you want to search : ";
cin>>target;


int min=0;
int max=sizeof(a)/sizeof(int)-1;
while( min <= max && min >=0 && max <=sizeof(a)/sizeof(int)-1)
{
int mid =(min+max)/2;
if(a[mid] == target)
{
cout<<"Found at index "<<mid;
exit(0);
}
else if(a[mid] >= a[min])
{
if(a[min] <= target && target <= a[mid])
{
max=mid-1;
}
else
{
min=mid+1;
}
}
else if(a[mid] <= a[max])
{
if(a[mid] <= target && target <= a[max])
{
min=mid+1;
}
else
{
max=mid-1;
}
}

}
}


Posted by at No comments:

Program 23RD in C++ VERSION 2


PROBLEM STATEMENT :

What is the diameter of a tree?

SOLUTION :

#include <iostream.h>
#include <cstdio>

using namespace std;

int flag = 1;

struct node
{
int data;
node *left;
node *right;
};

node* node(int n)
{

struct node* m = (struct node*)malloc(sizeof(struct node));

m->data=n;
m->left=NULL;
m->right=NULL;

return m;
}

int max(int a, int b)
{

return a>b?a:b;

}

int diameter(struct node* n, int* height)
{

int lh=0;
int rh=0;
int ld=0;
int rd=0;

if(n == 0)
{
*height=0;
return 0;
}

if(n->left == 0 && flag == 1)
{
n=n->right;
return diameter(n,height);
}
else if (n->right == 0 && flag == 1)
{
n=n->left;
return diameter(n,height);
}
else
{
flag=0;
}

ld = diameter (n->left,&lh);
rd = diameter (n->right,&rh);

*height=max(lh,rh)+1;

return (max(lh+rh+1,max(ld,rd)));
}

int main()
{

struct node* root = node(0);
root->right=node(1);
root->right->left=node(7);
root->right->right=node(2);
root->right->right->right=node(3);
root->right->right->right->left=node(4);
root->right->right->right->right=node(5);

int height;

cout<<diameter(root,&height);

}

Posted by at No comments:

Program 23RD in C++ VERSION 1


PROBLEM STATEMENT :

What is the diameter of a tree?

SOLUTION :

#include <iostream.h>
#include <cstdio>

using namespace std;

int flag=1;

struct node
{
int data;
node* left;
node* right;
};

int max(int a, int b)
{

return (a > b ? a : b);

}

int height(node* n)
{

if(n == 0)
{
return 0;
}
else
{
return 1+max(height(n->left),height(n->right));
}

}

node* node(int val)
{

struct node* m=(struct node*)malloc(sizeof(struct node));
m->data=val;
m->left=NULL;
m->right=NULL;

return m;
}

int diameter(struct node* n)
{
if(flag == 1 && n->left == 0)
{
n=n->right;
return diameter(n);
}
else if (flag == 1 && n->right == 0)
{
n=n->left;
return diameter(n);
}
else
{
flag = 0 ;
}
if(n == 0)
{
return 0;
}
int lh = height(n->left);
int rh = height(n->right);

int ld = diameter(n->left);
int rd = diameter(n->right);
return(max(lh+rh+1,max(ld,rd)));
}

int main()
{

struct node* root;
root = node(0);
root->left = node(1);
root->right = node(7);
root->right->right = node(4);
//root->right->left = node(7);
root->right->right->right = node(3);
//root->right->right->right->left = node(8);
root->right->right->right->right = node(2);

cout<<diameter(root);
}
Posted by at No comments:

Program 22ND in C++

PROBLEM STATEMENT :


How to compute A^n where n<1 million
Write code...

SOLUTION :

#include <iostream.h>
#include <cstdio>

using namespace std;

long double power(long double num, long int pow)
{

int flag = pow >=0 ? 0 : 1;

//long double one= 1.0F;
if(flag != 0)
{
pow*=-1;
num=1/(num);
}
if(pow == 0L)
{
return 1;
}
else if(pow == 1L)
{
return num;
}
else if(pow % 2 == 0)
{
return power(num,pow/2)*power(num,pow/2);
}
else
{
return power(num,pow/2)*power(num,pow/2)*num;
}
}
int main()
{

cout<<power(2,12345)<<endl;
cout<<power(2,51)<<endl;
cout<<power('\0','\0')<<endl;
cout<<power(2,0)<<endl;
cout<<power(2,-2);

}


Posted by at No comments:

Program 21ST in C++ VERSION 2

PROBLEM STATEMENT :

Find the longest palindrome in a given string

SOLUTION :

//solves in o(n^2)

#include <cstdio>
#include <iostream.h>
#include <string.h>

using namespace std;

string find(string s2,int i, int j)
{
int l=i;
int r=j;
int length=s2.length();

while(i>=0 && j<length && s2[i] == s2[j])
{
i--;
j++;

}

return s2.substr(i+1,j-i-1);

}
void palin(string s)
{

int l=s.length();

if(s.length() == 0)
{
cout<<" ";
}

string longest = s.substr(0,1);

for(int i=0; i
{
string s1=find(s,i,i);
if(s1.length() > longest.length())
{
longest=s1;
}

s1=find(s,i,i+1);
if(s1.length() > longest.length())
{
longest=s1;
}
}

cout<<"LONGEST PALINDROME IS : "<<longest;
}

int main()
{

string s;
cout<<"Enter a string : ";
getline(cin,s,'\n');
palin(s);

}

Posted by at No comments:
Subscribe to: Posts (Atom)