Вопрос интервью - Поиск номеров

Question

Я только что получил этот вопрос на собеседовании по позиции SE, и я не совсем уверен, как на него ответить, кроме грубой силы:

Учитывая натуральное число N, найдите два числа, A и P, таких что:

N = A + (A + 1) + (A + 2) + ... + (A + P-1)

P должно быть максимально возможным.

Пример: для N = 14, A = 2 и P = 4

N = 2 + (2 + 1) + (2 + 2) + (4 + 2-1) N = 2 + 3 + 4 + 5

Есть идеи?

Answer 1

Если N четное / нечетное, нам нужно четное / нечетное количество нечетных чисел в сумме. Это уже наполовину число возможных решений. Например. для N = 14 нет смысла проверять любые комбинации, где P нечетно.

Переписав приведенную формулу, получим:

N = A + (A+1) + (A+2) + ... + (A+P-1)
    = P*A + 1 + 2 + ... + (P-1)
    = P*A + (P-1)P/2 *
    = P*(A + (P-1)/2)
    = P/2*(2*A + P-1)

Последняя строка означает, что N должно делиться на P / 2, это также исключает ряд возможностей. Например. 14 имеет только эти делители: 1, 2, 7, 14. Таким образом, возможные значения для P будут 2, 4, 14 и 28. 14 и 28 управляются нашими по очевидным причинам (фактически, любой P выше N / 2 может быть игнорируется).

Это должно быть намного быстрее, чем метод грубой силы.

(* сумма первых n натуральных чисел равна n (n + 1) / 2)

Answer 2

С вопросами об интервью часто разумно подумать о том, что, вероятно, является целью вопроса. Если бы я задавал вам этот вопрос, это не потому, что я думаю, что вы знаете решение, но я хочу видеть, как вы находите решение. Переформулировать проблему, сделать выводы, придумать то, что известно, ... это то, что я хотел бы видеть.

• Если вы просто сядете и скажете мне: «Я не знаю, как это решить», вы сразу же провалите интервью.

• Если вы скажете: я знаю, как решить это с помощью грубой силы, и я знаю, что это будет, вероятно, медленно, я дам вам несколько советов или помогу вам начать. Если это не помогает, вы, скорее всего, потерпите неудачу (если вы не продемонстрируете какие-то экстраординарные навыки, чтобы компенсировать тот факт, что вам, вероятно, не хватает чего-то в области общего анализа проблем, например, вы покажете, как реализовать решение, парализованное для многих ядер или реализованное на графическом процессоре).

• Если вы принесете мне готовое решение, но вы не сможете его найти, я дам вам еще одну похожую проблему, потому что меня не интересует решение, мне интересно ваше мышление.

Answer 3

A + (A+1) + (A+2) + ... + (A+P-1) упрощается до P*A + (P*(P-1)/2) или P*(A+(P-1)/2).

Таким образом, вы можете просто перечислить все делители N, а затем проверить каждый делитель P на следующее:

Является ли A = (N-(P*(P-1)/2))/P (решено первое упрощение для A) целым числом? (Я предполагаю, что это должно быть целое число, иначе это будет тривиально.) Если это так, верните его как решение.

Answer 4

Вот решение O (n).

Используется свойство суммы арифметической прогрессии. S = разница * (первый_терм + последний_терм) / 2

Здесь наша сумма равна N, разница равна P, а первое слагаемое равно A.

Манипулируя вышеприведенным уравнением, мы получаем некоторые уравнения, и мы можем перебрать P от 1 до n - 1, чтобы получить действительное A.

def solve(n,p):
return (2*n - (p**2) + p)/(2*p)

def condition(n,p,a):
if (2*n == (2*a*p) + (p**2) - p) and (a*-1 < 0):
    return True
else:
    return False

def find(n):
for x in xrange(n,-1,-1):
    a = solve(n,x)
    if condition(n,x,a):
        return n,x,a

Answer 5

Может быть решено с помощью 0-1 рюкзака.

Наблюдение: N / 2 + N / 2 + 1> N

так что наша серия 1,2, ..., N / 2

Рассмотрим ограничения W = N и vi = 1 для всех элементов, я думаю, что это тривиально отображается в ранце 0-1, O (n ^ 2)