Skip to content

1533. Find the Index of the Large Integer 👍

Approach 1: Straightforward

  • Time: $O(\log n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * // This is the ArrayReader's API interface.
 * // You should not implement it, or speculate about its implementation
 * class ArrayReader {
 *  public:
 *   // Compares the sum of arr[l..r] with the sum of arr[x..y]
 *   // return 1 if sum(arr[l..r]) > sum(arr[x..y])
 *   // return 0 if sum(arr[l..r]) == sum(arr[x..y])
 *   // return -1 if sum(arr[l..r]) < sum(arr[x..y])
 *   int compareSub(int l, int r, int x, int y);
 *
 *   // Returns the length of the array
 *   int length();
 * };
 */

class Solution {
 public:
  int getIndex(ArrayReader& reader) {
    int l = 0;
    int r = reader.length() - 1;

    while (l < r) {
      const int m = (l + r) / 2;
      if ((r - l) % 2 == 0) {
        const int res = reader.compareSub(l, m - 1, m + 1, r);
        if (res == 0)
          return m;
        if (res == 1) {
          r = m - 1;
        } else {  // res == -1
          l = m + 1;
        }
      } else {
        const int res = reader.compareSub(l, m, m + 1, r);
        // res is either 1 or -1.
        if (res == 1) {
          r = m;
        } else {  // res == -1
          l = m + 1;
        }
      }
    }

    return l;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * // This is ArrayReader's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface ArrayReader {
 *   // Compares the sum of arr[l..r] with the sum of arr[x..y]
 *   // return 1 if sum(arr[l..r]) > sum(arr[x..y])
 *   // return 0 if sum(arr[l..r]) == sum(arr[x..y])
 *   // return -1 if sum(arr[l..r]) < sum(arr[x..y])
 *   public int compareSub(int l, int r, int x, int y) {}
 *
 *   // Returns the length of the array
 *   public int length() {}
 * }
 */

class Solution {
  public int getIndex(ArrayReader reader) {
    int l = 0;
    int r = reader.length() - 1;

    while (l < r) {
      final int m = (l + r) / 2;
      if ((r - l) % 2 == 0) {
        final int res = reader.compareSub(l, m - 1, m + 1, r);
        if (res == 0)
          return m;
        if (res == 1) {
          r = m - 1;
        } else { // res == -1
          l = m + 1;
        }
      } else {
        final int res = reader.compareSub(l, m, m + 1, r);
        // res is either 1 or -1.
        if (res == 1) {
          r = m;
        } else { // res == -1
          l = m + 1;
        }
      }
    }

    return l;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# """
# This is ArrayReader's API interface.
# You should not implement it, or speculate about its implementation
# """
# class ArrayReader(object):
# # Compares the sum of arr[l..r] with the sum of arr[x..y]
# # return 1 if sum(arr[l..r]) > sum(arr[x..y])
# # return 0 if sum(arr[l..r]) == sum(arr[x..y])
# # return -1 if sum(arr[l..r]) < sum(arr[x..y])
#   def compareSub(self, l: int, r: int, x: int, y: int) -> int:
#
# # Returns the length of the array
#   def length(self) -> int:
#


class Solution:
  def getIndex(self, reader: 'ArrayReader') -> int:
    l = 0
    r = reader.length() - 1

    while l < r:
      m = (l + r) // 2
      if (r - l) % 2 == 0:
        res = reader.compareSub(l, m - 1, m + 1, r)
        if res == 0:
          return m
        if res == 1:
          r = m - 1
        else:  # res == -1
          l = m + 1
      else:
        res = reader.compareSub(l, m, m + 1, r)
        # res is either 1 or -1.
        if res == 1:
          r = m
        else:  # res == -1
          l = m + 1

    return l

Approach 2: if Compression

  • Time: $O(\log n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * // This is the ArrayReader's API interface.
 * // You should not implement it, or speculate about its implementation
 * class ArrayReader {
 *  public:
 *   // Compares the sum of arr[l..r] with the sum of arr[x..y]
 *   // return 1 if sum(arr[l..r]) > sum(arr[x..y])
 *   // return 0 if sum(arr[l..r]) == sum(arr[x..y])
 *   // return -1 if sum(arr[l..r]) < sum(arr[x..y])
 *   int compareSub(int l, int r, int x, int y);
 *
 *   // Returns the length of the array
 *   int length();
 * };
 */

class Solution {
 public:
  int getIndex(ArrayReader& reader) {
    int l = 0;
    int r = reader.length() - 1;

    while (l < r) {
      const int m = (l + r) / 2;
      const int res = (r - l + 1) % 2 == 0 ? reader.compareSub(l, m, m + 1, r)
                                           : reader.compareSub(l, m, m, r);
      if (res == -1)
        l = m + 1;
      else  // res == 1 || res == 0
        r = m;
    }

    return l;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * // This is ArrayReader's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface ArrayReader {
 *     // Compares the sum of arr[l..r] with the sum of arr[x..y]
 *     // return 1 if sum(arr[l..r]) > sum(arr[x..y])
 *     // return 0 if sum(arr[l..r]) == sum(arr[x..y])
 *     // return -1 if sum(arr[l..r]) < sum(arr[x..y])
 *     public int compareSub(int l, int r, int x, int y) {}
 *
 *     // Returns the length of the array
 *     public int length() {}
 * }
 */

class Solution {
  public int getIndex(ArrayReader reader) {
    int l = 0;
    int r = reader.length() - 1;

    while (l < r) {
      final int m = (l + r) / 2;
      final int res = (r - l + 1) % 2 == 0 ? reader.compareSub(l, m, m + 1, r) //
                                           : reader.compareSub(l, m, m, r);
      if (res == -1)
        l = m + 1;
      else // res == 1 || res == 0
        r = m;
    }

    return l;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# """
# This is ArrayReader's API interface.
# You should not implement it, or speculate about its implementation
# """
# class ArrayReader(object):
# # Compares the sum of arr[l..r] with the sum of arr[x..y]
# # return 1 if sum(arr[l..r]) > sum(arr[x..y])
# # return 0 if sum(arr[l..r]) == sum(arr[x..y])
# # return -1 if sum(arr[l..r]) < sum(arr[x..y])
#   def compareSub(self, l: int, r: int, x: int, y: int) -> int:
#
# # Returns the length of the array
#   def length(self) -> int:
#


class Solution:
  def getIndex(self, reader: 'ArrayReader') -> int:
    l = 0
    r = reader.length() - 1

    while l < r:
      m = (l + r) // 2
      res = (reader.compareSub(l, m, m + 1, r) if (r - l + 1) % 2 == 0
             else reader.compareSub(l, m, m, r))
      if res == -1:
        l = m + 1
      else:  # res == 1 or res == 0
        r = m

    return l