Найдите победителя, когда игроки удаляют кратные числа A или B из массива за каждый ход.

Дан массив arr размера N , а также то, что Алиса и Боб играют в игру, и у Алисы есть число A , а у Боба есть число B. У них обоих есть чередующиеся ходы, начиная с Алисы . В каждый ход текущий игрок должен удалить ненулевое количество элементов из массива, и каждый удаленный элемент должен быть кратен числу, данному этому игроку. Если невозможно удалить какие-либо элементы, то текущий игрок проигрывает игру. Узнайте, кто из игроков выигрывает игру.

Пример:

Input: N = 5, A = 3, B = 2, arr[] = {-1, 2, 3, 4, 5}
Output: Bob
Explanation: Alice first removes 3 then the sequence becomes [1, 2, 4, 5]. 
Bob removes 4 then the sequence becomes [1, 2, 5]. 
Now Alice cannot remove any number because sequence does not have any multiple of A.

Input:  N = 6, A = 2, B = 3, arr[] = {2, 4, 6, 3, 9, 12}
Output: Alice
Explanation: Alice first removes 6 and 12 then array becomes [2, 4, 3, 9]. 
Now Bob removes 3. Then ALice removes 2. arr[] becomes [4, 9].
Again Bob removes 9 and Alice removes 4. 
Then there is no element left. So Alice wins.

Наивный подход: начать поиск элемента в массиве, кратного заданному игроку числу (Алиса, Боб). Если элементы найдены, удалите эти элементы из заданного массива. Если не удастся найти это число, то этот игрок проиграет.

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

Эффективный подход: проблема может быть решена на основе следующей идеи:

• Count the number of multiples of only A and only B present in array arr[] also the elements divisible by both A and B. 
• The elements having both A and B as their factor can be removed in one turn by Alice. So consider those as a single unit to be removed in one turn by Alice.
• Now if the total number of elements present for Alice is greater then she wins, else Bob is the winner.

Выполните шаги, указанные ниже:

• Подсчитайте кратность заданных чисел игрокам в массиве arr. скажем, только A для Алисы и только B для Боба и оба AB для кратных A и B.
• Перебрать массив arr
  • Проверьте, кратен ли arr[i] как A, так и B.
    • Если это правда, то увеличивайте счетчик обоих AB .
  • Проверьте, является ли arr[i] кратным только A .
    • Если true, то увеличить счетчик onlyA .
  • Проверьте, кратен ли arr[i] только B .
    • Если true, то увеличить счетчик onlyB .
• Если оба AB больше 0 , тогда включите это как единую единицу, которую Алиса может удалить.
• Следовательно, в конечном итоге проверьте, может ли Алиса удалить больше, чем Боб, тогда Алиса выигрывает, в противном случае Боб.

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

Сложность времени: НА)
Вспомогательное пространство: О(1)