HappyLittlePony's blog

By HappyLittlePony, 6 years ago, In English

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:-)

  • Vote: I like it
  • +5
  • Vote: I do not like it

6 years ago, # |
  Vote: I like it -13 Vote: I do not like it

In this case : B r u t e f o r c e

Thank do not need ((:

6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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 :)

6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 here

The brute force solution is O(n) while Elucid's GCD is O(logn)