Table of Contents

## Problem Statement

In the “Find the point where a monotonically increasing function becomes positive first time” we have given a function **“int f(unsigned int x)”** which takes a **non-negative integer** ‘x’ as input and returns an **integer **as output. The function is monotonically increasing with respect to the value of x, i.e., the value of f(x+1) is greater than f(x) for every input x. Find the value ‘n’ where f() becomes positive for the first time. Since f() is monotonically increasing, values of f(n+1), f(n+2),… must be positive and values of f(n-2), f(n-3), .. must be negative. Our aim is to find n in O(logn) time. You may assume that f(x) can be evaluated in O(1) time for any input x.

## Input Format

The first and only one line containing a function f(x).

## Output Format

The first and only one line containing an integer value denotes a point where a monotonically increasing function becomes the positive first time.

## Example

x^2 - 4x - 8

6

**Explanation: **The value x where f(x) becomes positive is 6.

## Algorithm

In this method, the main idea is to apply a binary search, but for binary search, we need low and high values. Below algo shows how to find the values and implement binary search.

**1.** Till f(i) is greater than zero, double the i value. Once f(i) is greater than zero, then take i as the high and i/2 as the low.

**2.** Now search for the first positive value of f(i) in between i/2 and i. Binary search

**3.** Till high greater than or equal to high, find the mid

- If f(mid) is greater than zero and mid is equal to low or f(mid -1) is less than or equal to zero ie, f(mid>0) && (mid==low || f(mid-1) <=0), then return mid
- If f(mid) is less than zero, then search in the right half recursively.
- If f(mid) is greater than zero, then search in the left half recursively.

## Implementation

### C++ Program to Find the point where a monotonically increasing function becomes positive first time

#include<bits/stdc++.h> using namespace std; int binarySearch(int low, int high); int f(int x) { return (x*x - 10*x - 20); } int findFirstPositive() { if (f(0) > 0) return 0; int i = 1; while (f(i) <= 0) i = i*2; return binarySearch(i/2, i); } int binarySearch(int low, int high) { if (high >= low) { int mid = low + (high - low)/2; if (f(mid) > 0 && (mid == low || f(mid-1) <= 0)) return mid; if (f(mid) <= 0) return binarySearch((mid + 1), high); else return binarySearch(low, (mid -1)); } return -1; } int main() { cout<<findFirstPositive(); return 0; }

### Java Program to Find the point where a monotonically increasing function becomes positive first time

import java.util.ArrayList; import java.util.Scanner; class sum { public static int f(int x) { return (x*x - 10*x - 20); } public static int findFirstPositive() { if(f(0)>0) { return 0; } int i = 1; while(f(i)<=0) i = i * 2; return binarySearch(i / 2, i); } public static int binarySearch(int low, int high) { if (high >= low) { int mid = low + (high - low)/2; if (f(mid) > 0 && (mid == low || f(mid-1) <= 0)) return mid; if (f(mid) <= 0) return binarySearch((mid + 1), high); else return binarySearch(low, (mid -1)); } return -1; } public static void main(String[] args) { Scanner sr = new Scanner(System.in); findFirstPositive(); } }

x*x - 10*x - 20

12

## Complexity Analysis

### Time Complexity

**O(logn):** The number of steps for finding ‘high’ is O(Logn). So we can find ‘high’ in O(Logn) time. What about the time taken by Binary Search between high/2 and high? The value of ‘high’ must be less than 2*n. The number of elements between high/2 and high must be O(n). Therefore, the time complexity of Binary Search is O(Logn) and overall time complexity is 2*O(Logn) which is O(Logn)

### Space Complexity

**O(1)** because we don’t create any auxiliary space here.