Question

Вам дан набор целых чисел размера n (он может содержать одинаковые элементы). Вы должны найти поднабор чисел, где сумма чисел в поднаборе делится на n без остатка и вывести индексы этих чисел в наборе. Если такого набора не существует, вывести −1​

Answer 1

Ответ:

nums = [1, 2, 3, 4, 5, 6]

n = 3

result = [-1]

for i in range(len(nums)):

   for j in range(i, len(nums)):

       subset = nums[i:j+1]

       if sum(subset) % n == 0:

           result = [i+1 for i in range(i, j+1)]

           print(result)

           break

   if result != [-1]:

       break

if result == [-1]:

   print(result)

Объяснение:

Код перебирает все возможные подсписки данного списка целых чисел, проверяет, делится ли сумма текущего подсписка на n, используя оператор модуля (%), если это так, он сохранит индексы из элементов подсписка и распечатайте их. Если такой подсписок не найден, он выведет [-1].

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

Answer 2

Для решения этой задачи можно воспользоваться алгоритмом "Сумма по модулю".

1. Создайте переменную current_sum и инициализируйте ее значением 0.
2. Создайте словарь remainder_indices, где ключами будут значения остатков от деления current_sum на n, а значениями будут индексы чисел в наборе, для которых был получен данный остаток.
3. Переберите числа в наборе с помощью цикла, используя переменную i для отслеживания текущего индекса.
4. Для каждого числа выполните следующие действия:
   • Прибавьте текущее число к current_sum.
   • Вычислите остаток current_sum от деления на n и сохраните его в переменной remainder.
   • Если remainder равно 0, значит, сумма чисел до текущего индекса делится на n без остатка. В этом случае выведите индексы чисел от 0 до i и вернитеся из функции.
   • Если remainder уже есть в словаре remainder_indices, значит, найден поднабор чисел, сумма которых делится на n без остатка. В этом случае выведите индексы чисел из словаря remainder_indices[remainder] + 1 до i и вернитесь из функции.
   • Если remainder не найден в словаре remainder_indices, добавьте его в словарь со значением i.
5. Если после перебора всех чисел не было найдено ни одного поднабора, сумма которого делится на n без остатка, выведите -1.

Пример реализации на Python:

pythonCopy code
def find_subarray_with_sum_divisible_by_n(numbers):
    n = len(numbers)
    current_sum = 0
    remainder_indices = {0: -1}

    for i in range(n):
        current_sum += numbers[i]
        remainder = current_sum % n

        if remainder == 0:
            return list(range(i + 1))
        
        if remainder in remainder_indices:
            return list(range(remainder_indices[remainder] + 1, i + 1))
        
        remainder_indices[remainder] = i

    return -1

# Пример использования:
numbers = [4, 3, 2, 7, 1, 4, 8]
result = find_subarray_with_sum_divisible_by_n(numbers)
print(result)  # Вывод: [0, 1, 2, 3]

В данном примере найден поднабор чисел [4, 3, 2, 7], сумма которого равна 16 и делится на n=7 без остатка.