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.
@mos you are right
Here is a more simple solution with O(nlogn) complexity.
pseudo code
- blackice October 18, 2012