You want to compute the XOR of the following 9 sets: - numbers divisible by a and d - numbers divisible by a and e - numbers divisible by a and f - numbers divisible by b and d - numbers divisible by b and e - numbers divisible by b and f - numbers divisible by c and d - numbers divisible by c and e - numbers divisible by c and f
You can express XOR as a combination of AND and OR operations. For two sets: size(X XOR Y) = size(X OR Y) - size(X AND Y) For three sets: size(X XOR Y XOR Z) = size(X OR Y OR Z) - (size(X OR Y) + size(X OR Z) + size(Y OR Z)) + size(X AND Y AND Z). There is a similar, but more complicated expression for 9 sets. igor On Tue, Apr 3, 2012 at 1:18 AM, vivek dhiman <[email protected]> wrote: > Than you Igor. > But can you explain the last addition.. > > > > On Tue, Apr 3, 2012 at 12:09 AM, Igor Naverniouk <[email protected]>wrote: > >> Inclusion-Exclusion principle. >> >> Add all the numbers that are divisible by >> - a and d >> - a and e >> - a and f >> - b and d >> - ... >> - c and f >> >> Subtract all the numbers that are divisible by >> - a, b and d >> - a, c and d >> - b, c and d >> - ... >> - c, e and f >> >> Add back all the numbers that are divisible by >> - a, b, c and d >> - ... >> - c, d, e and f. >> >> ... >> >> igor >> >> On 2 April 2012 11:36, vivek dhiman <[email protected]> wrote: >> >>> Hi all smart people. >>> >>> if there are two set of numbers (both sets are of size 3) >>> (a,b,c) and (d,e,f) >>> >>> given a number k, how will you count all numbers(n) < k that are >>> divisible by both x and y >>> where x is any number from set (a,b,c) >>> and y is any number from set (d,e,f) >>> >>> remember you should take care of repetitions.. >>> >>> Thing is I am doing this using sets and iterators which is taking much >>> more time ..suggest some better approach .. >>> No need to write code... just the approach.. >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Google Code Jam" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> For more options, visit this group at >>> http://groups.google.com/group/google-code?hl=en. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Google Code Jam" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/google-code?hl=en. >> > > > > -- > Regards > Vivek Dhiman > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/google-code?hl=en. > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
