I am gonna make account of good observations and ideas which I come across while solving problems. The proofs of below statements will not be mentioned here, Its advised to do such proofs on own for exercise.
- Lets say I have a set $$$S$$$ consisting of integers, denote its $$$lcm(S) = L$$$, I add a new element $$$x$$$ to this set $$$S$$$ , Lets deonte the new set as $$$S'$$$,where $$$S' = union(S , x)$$$ and its $$$lcm(S') = L'$$$. Can we deduce a relation between $$$L$$$ and $$$L'$$$. We can observe that either $$$L = L'$$$ or $$$L' >= 2*L$$$.
- Lets say we want to find 2 numbers in an array $$$A[]$$$ which have maximum common prefix bits in binary representation. Its easy to show that those 2 numbers always occur as adjacent numbers in $$$sorted(A[])$$$
- The number of distinct gcd prefixed / suffixed at a index in array will never exceed $$$log(A_{max})$$$