## blackice

BAN USER@eugene: you are right on that

@anonymous: as I posted the solution, you need to extend on the equation you reached,

for all non zero remainder let that be total of x

sum of all remainder <= x*K

if (sum of all remainder == x*K) then n/2 pairs exits

1, 1, 1, 1, 1, 1, 3, 3 and K=4

% 4 is

1, 1, 1, 1, 1, 1, 3, 3 here x = 8

(1 + 1 + 1+ 1+ 1+ 1+ 3 + 3) != 8*4

hence n/2 pairs dont exists

The solution proposed works pretty well...

After create a replica with regular next links

insert then given linked list into the new replica in a way that node1 of original comes before the node1 of replica.

Let me name node1 of original as node1_orig and

node1 of replica as node1_rep.

node1_rep->rand = node1_orig->rand->next;

After which we can remove the alternating original node to get the replica with with random pointers.

As we have integers we can have +ve and -ve numbers

We can build a bitmap actually 2 bitmaps one for +ve and one for -ve

We simple mod a -ve number to get the position in a bitmap.

Build bit map for both the arrays and then "AND" them together.

Which ever bit is set to one is the common number.

Any repeating integer in single array can be rejected. This can be looked at a more compress hashmap.

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

@mos you are right

Here is a more simple solution with O(nlogn) complexity.

pseudo code

- blackice October 18, 2012