Simple approach to solve in exactly O(n) time without without cyclic traversal


#1

To solve this problem, we need to keep track of two things while we traverse the lists from 1 to n:

  1. total : Total of A[i] - B[i] for all values of i from 1 to n
  2. start: the last position which will total up to a positive value till the end, if counting is started from that position.

If total is negative,
return -1;
else,
return start;

Code: