HappyLittlePony's blog

By HappyLittlePony, 6 years ago,

Simple question:How to write easy-to-implement brute force solutions? Which techniques do you use (like using next_permutation)?

 » 6 years ago, # |   0 Hi, let's understand brute force using this simple example. Given 2 numbers A and B , find the Greatest Common Divisor(Highest Common factor).So, lets say you decide to iterate through every possible number  <  = min(A, B) and check if the number divides both A and B. Then you keep the maximum number to do so as your answer. In an increasing for loop, that would be the latest number to follow the above condition. a,b : input for i = 1 to min(a,b) if a and b divisible by i ans = i print ans This solution is called the brute force solution. Why ? Because you are basically iterating through every possible number to check the answer. Most of the numbers won't divide both A and B, which is a waste of precious computation time. Due to this they have the worst time complexity of all the solution present for a problem.An optimal method to find GCD is to use Elucid's algorithm, the details of which can be found hereThe brute force solution is O(n) while Elucid's GCD is O(logn)