Find element position in given monotonic sequence | Python 3 implementation of the approach ; Function to return the value of f ( n ) for given values of a , b , c , n ; if c is 0 , then value of n can be in order of 10 ^ 15. if c != 0 , then n ^ 3 value has to be in order of 10 ^ 18 so maximum value of n can be 10 ^ 6. ; for efficient searching , use binary search . ; Driver code
from math import log2 , floor NEW_LINE SMALL_N = 1000000 NEW_LINE LARGE_N = 1000000000000000 NEW_LINE def func ( a , b , c , n ) : NEW_LINE INDENT res = a * n NEW_LINE logVlaue = floor ( log2 ( n ) ) NEW_LINE res += b * n * logVlaue NEW_LINE res += c * ( n * n * n ) NEW_LINE return res NEW_LINE DEDENT def getPositionInSeries ( a , b , c , k ) : NEW_LINE INDENT start = 1 NEW_LINE end = SMALL_N NEW_LINE if ( c == 0 ) : NEW_LINE INDENT end = LARGE_N NEW_LINE DEDENT ans = 0 NEW_LINE while ( start <= end ) : NEW_LINE INDENT mid = ( start + end ) // 2 NEW_LINE val = func ( a , b , c , mid ) NEW_LINE if ( val == k ) : NEW_LINE INDENT ans = mid NEW_LINE break NEW_LINE DEDENT elif ( val > k ) : NEW_LINE INDENT end = mid - 1 NEW_LINE DEDENT else : NEW_LINE INDENT start = mid + 1 NEW_LINE DEDENT DEDENT return ans ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = 2 NEW_LINE b = 1 NEW_LINE c = 1 NEW_LINE k = 12168587437017 NEW_LINE print ( getPositionInSeries ( a , b , c , k ) ) NEW_LINE DEDENT