08 Smallest Number Which Never Becomes Negative | Array Problem | O(n) | DSA | Solution With Code

Given an array arr[]. Your task is to find the smallest number x such that when x is processed sequentially with each element of the array (from index 0 to n-1), it never becomes negative, under the following conditions:
- If x is greater than the current array element, x is increased by the difference between x and the array element.
- If x is less than or equal to the current array element, x is decreased by the difference between the array element and x.
Input: arr[] = [3, 4, 3, 2, 4]
Output: 4
Explanation: Start with `x = 4`:
- For arr[0] = 3, x becomes 5.
- For arr[1] = 4, x becomes 6.
- For arr[2] = 3, x becomes 9.
- For arr[3] = 2, x becomes 16.
- For arr[4] = 4, x becomes 28.
x remains positive throughout the process.
If x less than 4, it would become negative at some point.
00:00 Intro
00:20 Understanding the Problem with Example
06:45 Brute Force Approach - O(k*n)
18:20 Optimized Approach O(n)
27:45 C++ Implementation of above Algorithms
28:20 Code Execution for multiple Use Cases
30:00 Thank you
Comment if you need Complete Code link ...
👇Please Drop a comment with your thoughts, questions or ideas.🙏
👊Don't forget to like, share, and subscribe for more C/C++ programming content. Happy coding! 💻