Проверьте, можно ли сделать массивы равными, заменив элементы количеством цифр.

Опубликовано: 25 Февраля, 2023

Имея два массива A[] и B[] длины N, задача состоит в том, чтобы проверить, можно ли сделать оба массива равными, выполнив следующую операцию не более K раз:

  • Выберите любой индекс i и либо измените A i на количество цифр A i , либо измените B i к количеству цифр B у меня есть.

Примеры:

Input: N = 4, K = 1, A = [1, 2, 3, 4], B = [1, 2, 3, 5]
Output: Unequal
Explanation: It is impossible to make both the array equal by performing the following operation: 
1st operation on A will change A to [1, 2, 3, 1] as number of digit in 4 is 1. So both the arrays are unequal .

Input: N = 3, K = 3, A = [2, 9, 3], B = [1, 100, 9].
Output: Equal 
Explanation: It is possible to make both the array equal by performing the following operations: 
1st operation on A will change A to [1, 9, 3] as number of digits in 2 is 1.
2nd operation on B will change B to [1, 3, 9] as number of digit in 100 is 3.
So array A is equal to array B after the operations.

Подход: Чтобы решить проблему, следуйте следующей идее/интуиции:

Can we make both array similar? 

The answer is Yes as we are reducing each number by its length so eventually all numbers in both the array can be 1. The important thing here is to notice that every number greater than 1 always decreases by performing the operation. Thus, if a number appears in only one of the arrays, you will have to do one of the followings two things:

  • Decrease some greater number to make it equal to this one.
  • Decrease this number.

So, the proposed solution is the following. Consider the largest element in each array. If they are equal, remove both. If not, apply above operation to the larger of them and continue until the arrays are empty. This can be done efficiently using a max heap (priority queue).

Выполните следующие шаги, чтобы решить проблему:

  • Объявите приоритетную очередь (максимальная куча) «First» и поместите все элементы A[] в First .
  • Объявите очередь с приоритетом (максимальная куча) ' Second' и поместите все элементы B[] в Second .
  • Инициализируйте переменную счетчика в 0.
  • Запустите цикл while, пока какая-либо из очередей не станет пустой, и проверьте.
    • Если (First.top() > Second.top()), то извлеките верхний элемент из First и поместите количество цифр в этом элементе обратно в First и увеличьте счетчик на 1.
    • Если (Second.top() > First.top()), то извлеките верхний элемент из Second и поместите количество цифр в этом элементе обратно в Second и увеличьте счетчик на 1.
    • Если ( first.top() = second.top() ), то извлеките верхние элементы из обеих куч.
  • После завершения итерации, если счетчик меньше или равен K, выведите « Equal », иначе выведите « Unequal ».

Ниже приведена реализация описанного выше подхода.

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

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