CyberS1ren
BAN USERStudent at International Institute of Information Technology, Hyderabad
That's exactly what I am doing... In single iteration, I am computing both the sum and product... Now if all the numbers from 1 to 9 are present without any duplicates, the sum and product will come out to be as CSUM and CPROD... this is just a easy way to check the conditions for the sudoku board...
- CyberS1ren June 13, 2010#define CSUM 45
#define CPROD 362880
bool ValidateBoard(int a[9][9])
{
int i,j;
int Tsum, Tprod;
// Checking rows
for (i=0;i<9;i++)
{
Tsum = 0, Tprod = 1;
for (j=0;j<9;j++)
{
Tsum += a[i][j];
Tprod *= a[i][j];
}
if (Tsum != CSUM || Tprod != CPROD)
return false;
}
// Checking columns
for (j=0;j<9;j++)
{
Tsum = 0, Tprod = 1;
for (i=0;i<9;i++)
{
Tsum += a[i][j];
Tprod *= a[i][j];
}
if (Tsum != CSUM || Tprod != CPROD)
return false;
}
// Checking boxes
// Even with 4 nested loops, its O(n^2)
int m,n;
for (i=0;i<9;i+=3)
{
for (j=0;j<9;j+=3)
{
Tsum = 0, Tprod = 1;
for (m=i;m<i+3;m++)
{
for (n=j;n<j+3;n++)
{
Tsum += a[m][n];
Tprod *= a[m][n];
}
}
if (Tsum != CSUM || Tprod != CPROD)
return false;
}
}
return true;
}
List<int> FindNumbers(List<int> numbers, int key)
{
List<int> ans = new List<int>();
Dictionary<int,bool> seenNumbers = new Dictionary<int,bool>();
foreach (int n in numbers)
{
if (seenNumbers.ContainsKey(key - n))
{
ans.Add(n);
ans.Add(key-n);
break;
}
}
return ans;
}
int getDiameterCore(node *root, int *diameter)
{
if (root == NULL)
return -1;
int h1 = getDiameterCore(root->left,diameter);
int h2 = getDiameterCore(root->right,diameter);
if (h1+h2+2 > *diameter)
*diameter = h1+h2+2;
return 1+max(h1,h2);
}
int getDiameter(node *root)
{
int diameter = 0;
getDiameterCore(root,&diameter);
return diameter;
}
int getLevel(node *ptr)
{
int level = 0;
while (ptr)
{
level++;
ptr = ptr->parent;
}
return level;
}
node *getCommonAncestor(node *ptr1, node *ptr2)
{
int h1, h2, diff;
h1 = getLevel(ptr1);
h2 = getLevel(ptr2);
if (h1>h2)
{
diff = h1-h2;
while (diff-- && ptr1)
ptr1 = ptr1->parent;
}
else if (h2>h1)
{
diff = h2-h1;
while (diff-- && ptr2)
ptr2 = ptr2->parent;
}
while (ptr1 && ptr2)
{
if (ptr1->parent == ptr2->parent)
return ptr1->parent;
ptr1 = ptr1->parent;
ptr2 = ptr2->parent;
}
return NULL;
}
Finding level of a node takes O(log n) and not O(n) :)
- CyberS1ren November 26, 2009typedef node * NodePtr;
node *CreateListFromTree(node *root)
{
NodePtr start = NULL, tail = NULL;
CreateListFromTreeCore(root,&start,&tail);
return start;
}
/* Assume right for tree will act as next for Linked List */
void CreateListFromTreeCore(node *root, NodePtr *start, NodePtr *tail)
{
CreateListFromTreeCore(root->left,start,tail);
node *temp = root->right;
root->left = NULL;
if (*start == NULL)
*start = *tail = root;
else
{
(*tail)->right = root;
*tail = root;
}
*tail->right = *start;
CreateListFromTreeCore(temp,start,tail);
}
Great solution... :)
- CyberS1ren June 13, 2010