Разбить массив на группы по 3 так, чтобы X3 делилось на X2, а X2 делилось на X1.

Опубликовано: 14 Января, 2022

Для массива A, содержащего N элементов ( N делится на 3 ), задача состоит в том, чтобы разбить числа на группы по 3, пусть в группе будет 3 элемента X1, X2 и X3, для группы должны выполняться следующие условия:

  • X1, X2 и X3 попарно различны
  • X3 делится на X2
  • X2 делится на X1

Выведите -1, если разбить массив на N / 3 Такие группы невозможно.
Примечание. Элементы массива будут находиться в диапазоне от 1 до 6 (включительно).
Примеры:

 Ввод: N = 6, A [] = {2, 2, 1, 1, 4, 6}.
Выход : 1 2 4
         1 2 6
Пояснение : 
Группа 1 : пары = {(1,2), (2,4), (1,4)}
Все пары различны, 
4 делится на 2, а 2 на 1.
Группа 2 : пары = {(1,2), (2,6), (1,6)}
Все пары разные, 
6 делится на 2, а 2 на 1.

Ввод: N = 6, A [] = {1, 1, 1, 6, 6, 3}.
Выход: -1

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход:
Поскольку значения массива находятся в диапазоне от 1 до 6, можно создавать только следующие типы групп:

  • 1 2 4
  • 1 2 6
  • 1 3 6

Начните с подсчета частоты каждого элемента. Поскольку 1 является общим для всех групп, оно должно встречаться ровно N / 3 раз. 4 можно поместить только в группу первого типа, которая всегда содержит 2. Таким образом, количество 2 должно быть больше, чем количество 4. Остальные 2 могут быть помещены только в группы второго типа. Теперь оставшиеся числа нужно поместить в группы третьего типа. Если в какой-то момент счет меньше необходимого, ответ будет -1.
Ниже представлена реализация описанного выше подхода:

Сложность времени: O (N)

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

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