Recreate an array of m nonincreasing integers between 1-n in O(n) time with at most ⌈log n⌉ guesses per index & directional responses to wrong guesses

Question

In a game, your objective is to guess a number from the range 1 to n. You are allowed to make a maximum of ⌈log n⌉ guesses per round. Over the course of m rounds (where m < n), you record the correct answers in an array M[i], with i starting from 1 to m. Initially, designing an algorithm that runs in O(m*log(n)) time is straightforward. However, a new condition has been introduced: M[i] ≤ M[j] for all i > j, which means the answers are in descending order. The task is to find an algorithm that operates in O(n) time, given this modified condition.

Based on the condition M[i] ≤ M[j] for all i > j, I can narrow down the range between 1 to n. But in the worst case, I still cannot get O(n). Also, you cannot brutal force to guess the numbers, there is a limit on it.

Some clarifications: 1.When you guess, you are told it's too large or too small. (it's a classic binary search question) 2.The answers are in a descending order. 3.The limit of guessing times in each round is ⌈log n⌉, not log(n) + 1, sorry for my mistakes in the previous statement.

Let me give an example, hope this helps.

• Let's play a game, you need to guess an integer from 1 to 100 (n = 100).
• You need to play it 10 rounds (m = 10).
• In each round, you have ⌈log n⌉ guesses. I will tell you if your answer is too big or too small.
• The answer in next round is always equal to or less than previous round. Such as: {98,88,76,76,76,74,65,43,43,42}

Let me know if you need more info.

Thanks in advance!

Answer 1

Inputs:

• n: an integer
• M: a nonincreasing array of integers in the range 1-n, with 1 as the first index. |M| = m < n.

Goal: recreate M in sequence by making at most ⌈log n⌉ guesses per index, with a running time of O(n). I.e. we can't directly access M, but just guess a value of the first undetermined index and learn whether our guess is correct, or too big, or too small.

Notation:

• Let k = ⌈log n⌉, our max guesses per index.
• Let M' be the output array. Unlike the input array, for convenience this will be zero-indexed, with M'[0] = n. Our goal will be to have M'[i] = M[i] for 1 <= i <= n.

Procedure to determine M[i] given M[i-1]:

• guess 1: M[i-1] - k + 1
• case 1: If our first guess is correct, we're done.
• case 2: if our first guess is too small, the correct answer is one of the k-1 values between M[i-1] and M[i-1] - k + 2 inclusive. We will guess these in descending order.
• case 3: if our first guess is too large, the correct answer is between 1 and M[i-1] - k inclusive. We use binary search to determine the correct answer in at most k-1 additional steps, for a total of k.

First Constraint Analysis: guess each number in at most k = ⌈log n⌉ steps.

case 1 steps: 1

case 2 steps: M[i] - M[i-1] + 1 <= k

case 3: Binary search will take at most ⌈log n⌉ - 1 steps in the range 1 to n - ⌈log n⌉. Given that, this takes at most k steps (the initial guess, plus at most k-1 for binary search).

So this satisfies the first constraint, that each number is guessed in at most k steps.

Second Constraint Analysis: The algorithm should be O(n).

Let's say G[i] is the number of guesses we make to determine M[i]. Note that for all three cases, G[i] <= M[i-1] - M[i] + 1. In other words, if successive values of M differ by r, we will determine the latter value in at most r+1 guesses (never more than k, but we don't need that fact for this portion).

But the cumulative difference across all of M is at most n-1, and |M| < n, so the total number of guesses must be <= (n-1) + |M| < (n-1) + n = 2n-1 = O(n).