Hi,

This is an actual interview question asked in an HFT firm. Could someone here advise the correct approach to program these problems? I am just a newbie to data structures (primarily trees and BFS/DFS) and I am not sure what should be applied when. For example, does this problem involve the use of hash maps / trees?

Find a way to 'cut' an array with minimum 'cuts' such that every subarray generated from the cuts has a gcd larger than 1.

I can conver this to the following Math problem - If two numbers in the original array are co-prime to each other they should not be in the same set / sub-array. But, I am not sure how to approach further.

Thanks