Разбить массив на группы по 3 так, чтобы X3 делилось на X2, а X2 делилось на X1.
Для массива 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
Подход:
Поскольку значения массива находятся в диапазоне от 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.