HappyLittlePony's blog

By HappyLittlePony, 5 years ago,

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

Thank you for all answers:-)

• +5

 » 5 years ago, # |   -13 In this case : B r u t e f o r c eThank do not need ((:
 » 5 years ago, # |   -8 Read the problem,stick a smile on your face and start to type.By the time you finish i can truly say you will have a brute force solution on your screen :)
 » 5 years ago, # |   +1 For brute-force I use recursion 90% of the time. If you are brute-forcing something which state can be described by a permutation, then sure — go with next_permutation.But in general brute-force is not algorithm but an approach so it's hard to give you any real advice that will always work. In general I use backtracking with recursion and that's the most standard approach.
 » 5 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)
•  » » 4 weeks ago, # ^ |   0 This will definitely help to clear the doubts about bruteforce approach.