Prakhar | Blog

Problem Solving

Prakhar Srivastava | Jan. 6, 2024

Problem Solving is the process of 
-	defining a problem
-	finding the cause 
-	identifying a solution
-	working on alternative solutions
-	implementing a solution (well of course the best one).

Programmatically speaking, just like Mathematics, a problem can be solved in multiple ways.
Here is a very simple example of how the process of problem solving is brought into practice.

**Problem Statement: Find the sum of first 'n' natural numbers.**

**Solution 1. The Novice way**
```
def sum_n(n):
	s = 0
	for i in range(1, n+1):
		s += i
	return s
```
Space complexity = **O(1)**
Time complexity = **O(n)**

This solution has to iterate over each number in the range 1 to n hence, has a time complexity of O(n).

**Solution 2. The Python way**
```
def sum_n(n):
	return sum(range(1, n+1))
```
Space complexity = **O(1)**
Time complexity = **O(n)**

Even though we have reduced the lines of code in this solution, we are still using the in-built sum() method, which takes O(n) time to complete.

**Solution 3. The Jedi way**
```
def sum_n(n):
	return (n * (n+1)) / 2
```
Space complexity = **O(1)**
Time complexity = **O(1)**

This is the best approach amongst the three solutions discussed here. It makes use of the Mathematical formula for calculating the sum of 'n' Natural numbers, which has been derived using Arithmetic Progression.

```S = (a + l) / 2```

where,
	S = Sum of n numbers in range
	a = first term of the progression
	l = last term of the progression
 
 Doing this, we have brought down the time complexity to O(1), .i.e. your output does not depend on the size of the input anymore.

A few people might argue, "Why not use lambda for this?" Well, because:
i.	The space and time complexities will remain the same.
ii.	It will add an unnecessary layer of complication for such a straight forward calculation.

Here is the lambda approach for my dear Python enthusiasts:
Definition:

```sum_n = lambda n: (n * (n+1) / 2)```

Call:

```print(sum_n(10))	# sum from 1 to 10```

To conclude, we started with the brute-force solution, then tried to leverage language-specific features and at the end attained the best solution by applying knowledge from another domain.

Thanks for reading 😊.