Geek asks and answers

A number contained in an odd number of sets

I have a home problem that I can only solve in O(max(F)*N)( Nabout 10^5and Fis 10^9) difficulty, and I hope you could help me. I have been given Nsets of 4 integernumbers (called S, F, aand b); Each set of 4 numbers describes a set of numbers as follows: The first includes the following numbers, starting with S. The following bserial numbers are not, then the following numbers arepeat this until you reach the upper limit F. For example, for a S=5;F=50;a=1;b=19set contains a (5,25,45); S=1;F=10;a=2;b=1set contains(1,2,4,5,7,8,10);

I need to find an integer that is contained in an odd number of sets. It is guaranteed that for this test there is ONLY 1 number that complies with this condition.

I tried to go through each number between min(S)and max(F)and check how many sets are included in this number, and if it is included in an odd number of sets, then this is the answer. As I said, this way I get O (F*N)that too much, and I have no other idea how I can find out if a number is in an odd number of sets.

If you could help me, I would be very grateful. Thanks in advance and sorry for my poor english and explanation!

+3
source share
4 answers

prompt

I would have a desire to use a bisector.

x, , <= x .

, <= x, > x.

O (Nlog (F))

,

[S=1,F=8,a=2,b=1]->(1,2,4,5,7,8) 
[S=1,F=7,a=1,b=0]->(1,2,3,4,5,6,7) 
[S=6,F=8,a=1,b=1]->(6,8)

:

N (y) = y ,

C (z) = sum (N (y) y (1, z))% 2

y  N(y)  C(z)
1  2     0
2  2     0
3  1     1
4  2     1
5  2     1
6  2     1
7  2     1
8  2     1

, , C (z) 1.

+3

, , , . , . a b , , , S F: - S = max (S1, S2) F = min (F1, F2).

; , , a b.

+1

XOR .

XOR . I.e., "", "" .

, , , . XORed , .

, , - , . , , , , , .

+1

, S . O(max(F)*N), , .

Have an array of integers with a record for each candidate number (i.e. each number between min (S) and max (F)). Go through all fours and add 1 to all the cells in the array associated with the included numbers represented by each four. At the end, scroll through the array to see which count is odd. The number that it represents is the number that satisfies your conditions.

This works because you go into N fours, and each of them takes O (max (F)) or less time (provided that S is always non-negative) to count the numbers included. This gives you O (max (F) * N).

0
source

More articles:


All Articles