/* File: FindRoot.java - March 2018 */
package l04;

import java.util.function.*;

/**
 * Determines if there is an integer solution to the equation f(x) = n for
 * a positive integer n subject to the assumption that f is increasing,
 * positive, and f(Integer.MAX_VALUE ) > n
 *
 * Uses a recursive approach and some lambda functions.
 *
 * @author Michael Albert
 *
 */

public class FindRoot{

  public static Integer solution(IntFunction<Integer> f, int n) {
    int i = 1;
    int fi = f.apply(i);
    
    if (fi > n) {
      return null;
    }
    
    while (fi <= n) {
      i *= 2; fi = f.apply(i);      
    }
   
    return solutionInRange(f,n,i/2,i);
  }
  
  private static Integer solutionInRange(IntFunction<Integer> f, int n, int low, int high) {
    if (low >= high) return null;
    int mid = (low + high)/2;
    int fm = f.apply(mid);
    if (fm == n) return mid;
    if (fm < n) return solutionInRange(f, n, mid+1, high);
    return solutionInRange(f, n, low, mid);
  }
  
  public static void main(String[] args) {
  
    IntFunction<Integer> f = x -> x*x*x + x*x + 1;
    Integer k = solution(f, Integer.parseInt(args[0]));
    System.out.println(k);
  }

}