Find the point where a monotonically increasing function becomes positive first time

Difficulty Level Medium
Frequently asked in American Express
Binary Search Divide and Conquer SearchingViews 2009

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.

Translate »