Учитывая массив целых чисел, найдите БОЛЬШОЕ число, используя цифры массива, так что он делится на 3

Ответ 1

Наблюдение: Если вы можете получить число, которое делится на 3, вам нужно удалить не более 2 чисел, чтобы поддерживать оптимальное решение.

Простое решение O(n^2) будет проверять все возможности для удаления 1 числа, а если нет, проверьте все пары (из них O(n^2)).

EDIT: Решение O(n): создайте 3 ведра - bucket1, bucket2, bucket0. Каждый из них будет обозначать значение модуля 3 чисел. Игнорировать bucket0 в следующем алгоритме.

Пусть сумма массива будет sum.

If sum % 3 ==0: we are done.
else if sum % 3 == 1:
  if there is a number in bucket1 - chose the minimal
  else: take 2 minimals from bucket 2
else if sum % 3 == 2
  if there is a number in bucket2 - chose the minimal
  else: take 2 minimals from bucket1  

Примечание: вам действительно не нужно ведро, чтобы достичь пространства O(1) - вам нужны только 2 минимальных значения из bucket1 и bucket2, так как это единственный номер, который мы фактически использовали из этих ковшей.

Пример:

arr = { 3, 4, 0, 1, 5 }
bucket0 = {3,0} ; bucket1 = {4,1} bucket2 = { 5 }
sum = 13 ; sum %3 = 1
bucket1 is not empty - chose minimal from it (1), and remove it from the array.
result array = { 3, 4, 0, 5 } 
proceed to STEP 4 "as planned"

Ответ 2

Жадный выбор определенно не работает: рассмотрим набор {5, 2, 1}. Сначала вы удалите 1, но вы должны удалить 2.

Я думаю, вы должны разработать сумму массива modulo 3, которая либо 0 (вы закончили), либо 1, либо 2. Затем вы хотите удалить минимальное подмножество, сумма которого по модулю 3 равна 1 или 2.

Я думаю, что это довольно просто, поэтому реальной необходимости в динамическом программировании нет. Сделайте это, удалив одно число с этим модулем, если это возможно, в противном случае сделайте это, удалив два числа с другим модулем. Как только вы узнаете, сколько нужно удалить, выберите минимально возможное. Вам не нужно будет удалять три числа.

Вам не нужно специально обрабатывать 0, хотя, если вы собираетесь это сделать, вы можете дополнительно уменьшить рассматриваемый набор на шаге 3, если вы временно удалите из него все 0, 3, 6, 9.

Объединяя все это, я бы наверное:

• Сортировка цифр, по убыванию.
• Вычислите модуль. Если 0, мы закончили.
• Попробуйте удалить цифру с этим модулем, начиная с конца. В случае успеха мы закончили.
• Удалите две цифры с отрицательным модулем, начиная с конца. Это всегда удается, поэтому мы закончили.
• Мы можем оставить пустой массив (например, если вход 1, 1), и в этом случае проблема была невозможна. В противном случае массив содержит цифры нашего результата.

Сложность времени O(n) при условии, что вы выполните сортировку в шаге 1. Что вы, безусловно, можете, так как значения являются цифрами.

Ответ 3

Что вы думаете об этом:

сначала отсортировать элементы массива по значению

sum up all numbers
- if sum remainder after division by 3 is equal to 0, just return the sorted
  array
- otherwise
    - if sum of remainders after division by 3 of all the numbers is smaller
      than the remainder of their sum, there is no solution
    - otherwise
        - if it equal to 1, try to return the smallest number with remainder
          equal to 1, or if no such, try two smallest with remainder equal to 2,
          if no such two (I suppose it can happen), there no solution
        - if it equal to 2, try to return the smallest number with remainder
          equal to 2, or if no such, try two smallest with remainder equal to 1,
          if no such two, there no solution

сначала отсортировать элементы массива по остатку деления на 3 по возрастанию то каждое подмножество равного остаточного сорта по значению убывания

Ответ 4

Во-первых, эта проблема сводится к максимальному количеству выбранных элементов, так что их сумма делится на 3.

Тривиальный: выберите все числа, делящиеся на 3 (0,3,6,9).

Le a - элементы, которые оставляют 1 в качестве остатка, b - элементы, которые оставляют 2 в качестве остатка. Если (| a | - | b |)% 3 равно 0, тогда выберите все элементы из a и b. Если (| a | - | b |)% 3 равно 1, выберите все элементы из b и | a | -1 наивысших чисел из a. Если остаток равен 2, затем выберите все числа из a и | b | -1 самых высоких чисел из b.

Как только у вас есть все номера, сортируйте их в обратном порядке и соедините. это ваш ответ.

В конечном счете, если n - это число элементов, этот алгоритм возвращает число, которое, как минимум, n-1 цифр длиннее (за исключением угловых случаев, см. ниже).

ПРИМЕЧАНИЕ. Позаботьтесь о угловых случаях (то есть, что | a | = 0 или | b | = 0 и т.д.). (-1)% 3 = 2 и (-2)% 3 = 1.

Если m - размер алфавита, а n - количество элементов, этот мой алгоритм O (m + n)

Ответ 5

Сортировка данных не требуется, поскольку существует только десять различных значений. Просто подсчитайте количество нулей, единиц, двое и т.д. В O (n), если указаны n цифр. Рассчитайте сумму всех цифр, проверьте, является ли остаток по модулю 3 равным 0, 1 или 2.

Если остаток равен 1: Удалите первое из следующего, которое возможно (одно из них гарантировано): 1, 4, 7, 2 + 2, 2 + 5, 5 + 5, 2 + 8, 5 + 8, 8 + 8.

Если остаток равен 2: Удалите первое из следующего, которое возможно (одно из них гарантировано): 2, 5, 8, 1 + 1, 1 + 4, 4 + 4, 1 + 7, 4 + 7, 7 + 7.

Если цифр нет, проблема не может быть решена. В противном случае решение создается путем объединения 9, 8, 7 и так далее, сколько осталось.

(Сортировка n цифр займет O (n log n). Если, конечно, вы не сортируете, подсчитывая, как часто происходит каждая цифра и генерирует отсортированный результат в соответствии с этими числами).

Ответ 6

В ответе Амита крошечная вещь отсутствует.

Если bucket1 не пуст, но имеет большое значение, скажем, 79 и 97, а b2 также не пуст, а его минимальные значения 2, скажем, 2 и 5. Тогда в этом случае, когда модуль суммы все цифры равны 1, мы должны выбрать удаление 2 и 5 из ведра 2 вместо минимального в ковше 1, чтобы получить наибольшее сцепленное число.

Тестовый кейс: 8 2 3 5 78 79

Если мы будем следовать предложенным методам Амитса и Стива, наибольшее число будет 878532, тогда как наибольшее количество возможных делится на 3 в этом массиве - 879783

Решение заключалось бы в сопоставлении минимального минимального минимального количества ковша с конкатенацией минимальных значений другого ковша и устранения меньшего.