Brute Force

general
1

Can anybody tell me, what is meant by Brute Force solution of a problem?

2

By reading this, you will be able to understand that what is brute force solution.

2 Likes
3

Brute force is a crude algorithm which works through every possible answer until the correct one is found. Some problems can be solved this way but others- for instance obtaining the prime factors of large numbers or picking the best chess move, have far too many possibilities to be solved that way except in simple cases.

For example, searching an unsorted array to find the location of a value can be done in an average of n/2 searches if there are n elements in the array, That’s linear in Big-O Notation. But if you sort the array first and use a binary chop algorithm, then the search shortens to an average of Log2(n ) comparisons. An array of 1024 sorted values can be found in 10 comparisons or less.

2 Likes
4

@m1m9_94 >> Suppose I have asked you to go to a library to search for a book Quantum Mechanics. Now, you go to the library and starting from one rack (initial position) you kept searching throughout till you reached the end (final position) or till you found the book. --> This was a brute force searching.

Now, next time, I asked you, then you are a clever boy now, so you first thought Quantum Mechanics has nothing to do with Biology, Management, or Literature, so what you do is whenever you encounter these sections you ignore them, and you search in the respective sections. --> This is called directed search, and will take lesser time to search, in general.

For a problem, if a problem asks output the largest two digit integer which is divisible by 2 and 3

then from the first approach you went on from the first two digit integer i.e. 10 all the way to the largest two digit number i.e. 99 to check for a number which is divisible by 2 and 3 and keeping a variable max to store the maximum. After the loop, you have the answer. Next time, you started with 99, and went down till you got the first number which is divisible by 6 and you have the answer (96).

Yes, you guessed it right, first one was the brute force approach, second one was some smart move to save some time.

Now lets come to an example considering Codechef challenge problems. Many problems of the challenge format are solvable using brute force method. For example, if you look at the Password Cracking Challenge problem of May13 long contest then the brute force solution to that problem may be

1. Input T, N, H
2. Print a string N times, take an input
3. Repeat step #3 T times.

This indeed will give you a correct answer but with a low score, you have to obviously take other conditions into consideration and you’re supposed to optimize your code.

3 Likes
5

oh thank you i got it… :slight_smile: