Given Two arrays of n numbers. Find Whether they are disjoint or not.

Each Element lie in range [0,n^100] .

Space : O(n)

# | User | Rating |
---|---|---|

1 | tourist | 3882 |

2 | maroonrk | 3539 |

3 | Benq | 3513 |

4 | MiracleFaFa | 3466 |

5 | ksun48 | 3462 |

6 | ecnerwala | 3446 |

7 | slime | 3428 |

8 | Um_nik | 3426 |

9 | jiangly | 3401 |

10 | greenheadstrange | 3393 |

# | User | Contrib. |
---|---|---|

1 | awoo | 192 |

2 | -is-this-fft- | 191 |

3 | Monogon | 184 |

4 | YouKn0wWho | 182 |

4 | Um_nik | 182 |

6 | antontrygubO_o | 171 |

7 | maroonrk | 169 |

8 | kostka | 165 |

9 | SecondThread | 164 |

9 | errorgorn | 164 |

Given Two arrays of n numbers. Find Whether they are disjoint or not.

Each Element lie in range [0,n^100] .

Space : O(n)

↑

↓

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/24/2022 21:51:50 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

expected O(n)then this is just a hash-table problem.O(n)? , then it will getO(n*lgn)....Answer above question, and one more thing , can we do this using

bitwisekung-fu , like Xoring (just a guess) .Seems Correct.

So, Is there any other way ?

O(n*log(n^{100})) =O(nlog(n)) so it can't be solved inO(n) time. At least unless we have some special agreements about working with long numbers inO(1) time.Yes, You are given with that liberty.Here input size can be taken as

O(n).Although it should be

n*log(n)when considered, inbits.But Here Assume

log(n)is ignored and..we are working with long numbers inO(1).