educative.io

Educative

While it's hard to prove tight bound mathmatically

Well we’re all studying this course for a job interview, so it does make sense to make a computational approach to calculating TC of this problem.

For Java, the input is givien as an integer type, and int has at most 10 digits. We can prove this quite easily.

2^30 is bounded to 10^9, and positive integer value is bounded by 2 * 2^30, which means the actual decimal value for int we get at most 2 * 10^9, which indeed is 10 digit length.

With 10 digits, the maximum next number we can get is 10 * 81, which is 10 digits with all 9s. Therefore without actually using double pointers, we can solve this problem with embedding for loop with at most 810-ish repetitions.

If you actually try in code, we only need 50 or less repetitions. We still can’t say that the time complexity is logarithmic, however it’s more than enough discuss with your interviewer about above practical approach :wink:

1 Like