Найдите уникальные лексикографически возрастающие четверки с суммой B и НОД абсолютных значений всех элементов равным 1

Опубликовано: 22 Сентября, 2022

Дан массив A размера N и целое число B. Задача состоит в том, чтобы найти все уникальные четверки, расположенные в порядке лексикографического возрастания, так что сумма элементов каждой четверки равна B , а НОД абсолютных значений всех элементов массива вчетверо равно 1 .

Пример :

Input: A = {1, 0, -1, 0, -2, 2 }, B = 0
Output:
-2 -1 1 2
-1  0 0 1
Explanation: There are only three unique quadruplets which have sum = 0 which are {{-2, 0, 0, 2}, {-2, -1, 1, 2}, {-1, 0, 0, 1}} and out of these quadruplets only the second and the third quadrupled have gcd equal to 1.

Input: A = { 1, 5, 1, 0, 6, 0 }, B = 7
Output:
0 0 1 6
0 1 1 5

Подход: идея состоит в том, чтобы сохранить сумму каждой пары элементов в хэш-карте, затем выполнить итерацию по всем парам элементов, а затем найти хэш-карту, чтобы найти пары, такие, что сумма учетверенных становится равной B и gcd абсолютных значений всех элементов четверки равно 1 . Подробный подход с использованием hashmap обсуждался в этой статье. Следуйте инструкциям, чтобы решить проблему.

  • Вставьте сумму каждой пары элементов массива в хэш-карту mp.
  • Инициализируйте набор st, чтобы сохранить все четверки.
  • Пройдите массив от i = 0 до N-1
    • Пройдите массив от j = i+1 до N-1
      • Найдите все пары из хэш-карты, сумма которых равна B-A[i]-A[j]. Инициализируйте вектор пар v в mp[BA[i]-A[j]].
      • Пройдите через вектор v , используя переменную k
        • Если v[k].first или v[k].second равно либо i , либо j , перейдите к следующей итерации.
        • Сохраните элементы четверки во временном массиве. Отсортируйте временный массив. Если gcd всех элементов временного массива равен 1, вставьте временный массив в st.
  • Пройдите через множество st и выведите все четверки.

Временная сложность : O(N^3)
Вспомогательное пространство: O(N^2)

РЕКОМЕНДУЕМЫЕ СТАТЬИ