CareerCup

It is 2*2^31*2^31/32 ----> that is 2 arrays, each with (2^31 arraylength) no of rows and each row contains ((2^31)/32 ( integers)) as columns.

To represent the state, we need say 00 for 'O' and 11 for 'X' and 01 or 10 for 'empty'.

So one array stores the state of O as 0 and rest as1s,
and in, Other array store the stae of X as 1 and rest as 0s.

Now by superimposing both together you can get the logic!

I think you can store each line as an integer, that is composed by 32 bits. You can use each bit of the integer to represents a single square, if the bit is 0 then the square contains a O if it is 1 the square contains an X. In this case you would need 2^31 Integers to store the entire board. You can preprocess the board to store each configuration as "winning for X", "winning for O" or "Draw".

Obviously, this problem must use bit operation to store the stats sine at each cell we only has three status: empty (00), occupied by X(01), and occupied by O(10). So each cell can be stored by two bits. So we only need 2*2^31*2^31 bits to store the configure. That's right.

2 Arrays of 32 integers each.
In one array, the rows are stored, blanks are represented by 0
In another, the columns are stored, blanks are represented by 1

This is so that, the empty cells can be distinguished

Obviously, we can store 4 kind of lines consists of x or o signs. This is horizontal, vertical, and two diagonal kind of lines. For each line, store coordinates of its ends. Also, maintain hash table to map coordinates to collection of lines ending in particular point.
When putting particular symbol to some point, extract up to 8 lines ending at that point and update set of lines on the map in O(1) time.
Checks for winner in O(1) time.