Technical Articles

OEIS sequence - A276128

Description​

Definition of a(n): For a positive integer n, let the single-player game G(n) be as follows. x is a number in {1, 2, ..., n}, but unknown to the player. The player can guess as many times as he wants to determine the value of x. For each guess, the player can propose a possible value c in {1, 2, ..., n}, but such guess will cost the player c dollars. After each guess, the player will get response to show whether c<x, c=x, or c>x.
A guess strategy will consist a series of guesses to determine x. The cost of multiple guesses is defined to be the sum of the cost of each guess. The cost of guess strategy is defined to be the worse case of the cost of the guess series. The optimal guess strategy for the game G(n) is the guess strategy that has the minimum cost. a(n) is the cost of the optimal guess strategy.

Sequence

0, 1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 21, 24, 27, 30, 34, 38, 42, 46, 49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 86, 90, 94, 98, 102, 106, 110, 114, 119, 124, 129, 134, 139, 144, 149, 154, 160, 166, 172, 178, 182, 186, 190, 194, 198, 202, 206, 210, 214, 218, 222, 226, 230, 234, 238, 242, 246, 250, 254, 258, 262, 266, 270, 274, 278, 282, 286, 290

• View more about A276128 in OEIS

Leetcode Solutions

Single Number III

Problem

[View Problem in Leetcode] Find two unpaired numbers in a large number of paired numbers.

Solution

[View Zhiqing's Solution Article in Leetcode](Most Views/Upvotes)
Time Complexity: O(n), Space Complexity: O(1)

Add Digits

Problem

[View Problem in Leetcode] Find the digit root.

Solution

[View Zhiqing's Solution Article in Leetcode](Most Views/Upvotes)
Time Complexity: O(1), Space Complexity: O(1)

The Skyline Problem

Problem

[View Problem in Leetcode] Find the outer contour of multiple button-aligned rectangles.

Solution

[View Zhiqing's Solution Article in Leetcode]
Time Complexity: O(n log n), Space Complexity: O(n)

K-th Smallest in Lexicographical Order

Problem

[View Problem in Leetcode] Find the k-th smallest number in k-th smallest positive integer in lexicographical order.

Solution

[View Zhiqing's Solution Article in Leetcode]
Time Complexity: O((log n)²), Space Complexity: O(1)