Brute Force Approach [TOC]

1.1. Introduction

In this article, we will discuss what is Brute Force Algorithm and what are its pros and cons. Below given are some features of the brute force algorithm are:

It is an intuitive, direct, and straightforward technique of problem-solving in which all the possible ways or all the possible solutions to a given problem are enumerated.
Many problems solved in day-to-day life using the brute force strategy, for example exploring all the paths to a nearby market to find the minimum shortest path.
Arranging the books in a rack using all the possibilities to optimize the rack spaces, etc.
In fact, daily life activities use a brute force nature, even though optimal algorithms are also possible.

1.2. Pros:

The brute force approach is a guaranteed way to find the correct solution by listing all the possible candidate solutions for the problem.
It is a generic method and not limited to any specific domain of problems.
The brute force method is ideal for solving small and simpler problems.
It is known for its simplicity and can serve as a comparison benchmark.

1.3. Cons:

The brute force approach is inefficient. For real-time problems, algorithm analysis often goes above the O(N!) order of growth.
This method relies more on compromising the power of a computer system for solving a problem than on a good algorithm design.
Brute force algorithms are slow.
Brute force algorithms are not constructive or creative compared to algorithms that are constructed using some other design paradigms.

1.4. Conclusion

Brute force algorithm is a technique that guarantees solutions for problems of any domain helps in solving the simpler problems and also provides a solution that can serve as a benchmark for evaluating other design techniques, but takes a lot of run time and inefficient.

1.5. Practice

1.5.1. P1: Subarray with given sum

Given an unsorted array A of size N that contains only positive integers, find a continuous sub-array that adds to a given number S and return the left and right index(1-based indexing) of that subarray.

In case of multiple subarrays, return the subarray indexes which come first on moving from left to right.

Note:- You have to return an ArrayList consisting of two elements left and right. In case no such subarray exists return an array consisting of element -1.

Example 1:

Input:
N = 5, S = 12
A[] = {1,2,3,7,5}
Output: 2 4
Explanation: The sum of elements 
from 2nd position to 4th position 
is 12.

Example 2:

Input:
N = 10, S = 15
A[] = {1,2,3,4,5,6,7,8,9,10}
Output: 1 5
Explanation: The sum of elements 
from 1st position to 5th position
is 15.

Your Task You don't need to read input or print anything. The task is to complete the function subarraySum() which takes arr, N, and S as input parameters and returns an ArrayList containing the starting and ending positions of the first such occurring subarray from the left where sum equals to S. The two indexes in the array should be according to 1-based indexing. If no such subarray is found, return an array consisting of only one element that is -1.

Expected Time Complexity: O(N) Expected Auxiliary Space: O(1)

1.5.2. P2: Missing number in array

Given an array of size N-1 such that it only contains distinct integers in the range of 1 to N. Find the missing element.

Example 1:

Input:
N = 5
A[] = {1,2,3,5}
Output: 4

Example 2:

Input:
N = 10
A[] = {6,1,2,8,3,4,7,10,5}
Output: 9

Your Task You don't need to read input or print anything. Complete the function MissingNumber() that takes array and N as input parameters and returns the value of the missing number. Expected Time Complexity: O(N) Expected Auxiliary Space: O(1)

Dr.Hao