KrishKrish
BAN USERA B C
----------------
B B B
B B W - Ruled Out By B in Step 2.
B W B
B W W-{ Step 1:A's Turn: Decision1 : if this was the case . A would have said he is
wearing While, so this wasn't case, this option is ruled out , B can use this fact
when he makes a decision }
W B B { Step 2: B's Turn: When ever C is wearing White B is wearing Black, B would
have said he is wearing Block If C is wearing White , But this wasn't the case ,
therefore option 2 and option 6 is ruled out }
W B W
W W B - Ruled Out by B in Step 2.
Step 3: C knows that B wasnt able to answer , the only case where he wont be able to answer is when C is wearing a Black. Hence the answer ... C is wearing Black
represent the tree using arrays. if the parent is at Ith node, the left children will be at 2i and the right one will be at 2i + 1,
Using this representation you can traverse in both the directions without having parent pointers.
any comments ?
int maxRow(int arrayOfBool[][cols],int rows,int cols)
{
int i = 0 ,j = 0;
int maxR = -1;
while(i<rows && j<cols)
{
if(arrayOfBool[i][j])
{
maxR = i;//mar current row as the max row
j++; // go to next col
}
else // if u find zero , go to next row, keep the col num intact
i++; // go to next row
}
return maxR;
}
int maxRow(int arrayOfBool[][cols],int rows,int cols)
{
int i = 0 ,j = 0;
for(j=cols-1;j>=0;j--)
{
for(i=0;i<rows;i++)
{
if(arrayOfBool[i][j])
return (i+1);
}
}
return 0;
}
//worst case tc O(rows*cols) case: array with all zeroes
//best case O(1) // case array[rows-1][cols-1] = 1
your algo is expecting numbers in sorted order and unique elements in the list. take this example and solve it { 2,4,6,2,4,6}
- KrishKrish July 12, 2012