Find winner when players remove multiples of A or B from Array in each turn

0 0 5 minutes read

Given an array arr of size N, and also given that Alice and Bob are playing a game and Alice has a number A and Bob has a number B. They both have alternate turns starting with Alice. In each turn, the current player must remove a non-zero number of elements from the array and each removed element should be a multiple of the number given to that player. If it is impossible to remove any elements then the current player loses the game. Find out which player wins the game.

Example:

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.

Naive approach: Start searching the element in the array which is multiple of a given number to the player ( Alice, Bob). If elements are found then delete those elements from the given array. If unable to find that number then that player will lose.

Time Complexity: O(N²)
Auxiliary Space: O(1)

Efficient approach: The problem can be solved based on the following idea:

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.

Follow the steps mentioned below:

Count the multiples of the given numbers to players in array arr. say, onlyA for Alice and onlyB for Bob and bothAB for A and B multiples.
Iterate over the array arr
- Check if arr[i] is multiple of both A and B.
  - If true, then increment the count of bothAB.
- Check if arr[i] is multiple of only A.
  - If true, then increment the count of onlyA.
- Check if arr[i] is multiple of only B.
  - If true, then increment the count of onlyB.
If bothAB is greater than 0 then include that as a single unit which Alice can remove.
Therefore, Ultimately check if Alice can remove more than Bob then Alice wins otherwise Bob.

Below is the implementation of the above approach.

C++

// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the winner
string winner(int arr[], int a, int b, int n)
{
  int onlyA = 0, onlyB = 0, bothAB = 0;
 
  // Loop to find the count of multiples
  for (int i = 0; i < n; i++) {
    if (arr[i] % a == 0 && arr[i] % b == 0) {
      bothAB++;
    }
    else if (arr[i] % a == 0) {
      onlyA++;
    }
    else if (arr[i] % b == 0) {
      onlyB++;
    }
  }
 
  if (onlyA + (bothAB > 0 ? 1 : 0) > onlyB) {
    return "Alice";
  }
  else {
    return "Bob";
  }
}
 
// Driver code
int main()
{
  int N = 6;
  int arr[] = { 2, 4, 6, 3, 9, 12 };
  int A = 2, B = 3;
 
  // Function call
  cout << (winner(arr, A, B, N));
  return 0;
}
 
// This code is contributed by Rohit Pradhan

Java

// java code to implement the approach
 
class GFG {
 
    // Function to find the winner
    public static String winner(int[] arr,
                                int a, int b)
    {
        int onlyA = 0, onlyB = 0, bothAB = 0;
        int n = arr.length;
 
        // Loop to find the count of multiples
        for (int i = 0; i < n; i++) {
            if (arr[i] % a == 0
                && arr[i] % b == 0) {
                bothAB++;
            }
            else if (arr[i] % a == 0) {
                onlyA++;
            }
            else if (arr[i] % b == 0) {
                onlyB++;
            }
        }
 
        if (onlyA + (bothAB > 0 ? 1 : 0)
            > onlyB) {
            return "Alice";
        }
        else {
            return "Bob";
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int N = 6;
        int arr[] = { 2, 4, 6, 3, 9, 12 };
        int A = 2, B = 3;
 
        // Function call
        System.out.println(winner(arr, A, B));
    }
}

Python3

# Python program for the above approach
 
# Function to find the winner
def winner(arr, a, b, n):
    onlyA, onlyB, bothAB = 0, 0, 0
 
    # Loop to find the count of multiples
    for i in range(n):
        if (arr[i] % a == 0 and arr[i] % b == 0):
            bothAB += 1
 
        elif (arr[i] % a == 0):
            onlyA += 1
 
        elif (arr[i] % b == 0):
            onlyB += 1
 
    if (onlyA + (1 if bothAB > 0 else 0) > onlyB):
        return "Alice"
    else:
        return "Bob"
 
# Driver code
N = 6
arr = [2, 4, 6, 3, 9, 12]
A,B = 2,3
 
# Function call
print(winner(arr, A, B, N))
 
# This code is contributed by shinjanpatra

C#

// c# code to implement the approach
using System;
 
class GFG {
 
  // Function to find the winner
  static String winner(int[] arr, int a, int b)
  {
    int onlyA = 0, onlyB = 0, bothAB = 0;
    int n = arr.Length;
 
    // Loop to find the count of multiples
    for (int i = 0; i < n; i++) {
      if (arr[i] % a == 0 && arr[i] % b == 0) {
        bothAB++;
      }
      else if (arr[i] % a == 0) {
        onlyA++;
      }
      else if (arr[i] % b == 0) {
        onlyB++;
      }
    }
 
    if (onlyA + (bothAB > 0 ? 1 : 0) > onlyB) {
      return "Alice";
    }
    else {
      return "Bob";
    }
  }
 
  // Driver code
  public static int Main()
  {
    int N = 6;
    int[] arr = new int[] { 2, 4, 6, 3, 9, 12 };
    int A = 2, B = 3;
 
    // Function call
    Console.WriteLine(winner(arr, A, B));
    return 0;
  }
}
 
// This code is contributed by Taranpreet

Javascript

<script>
       // JavaScript program for the above approach
 
       // Function to find the winner
       function winner(arr, a, b, n) {
           let onlyA = 0, onlyB = 0, bothAB = 0;
 
           // Loop to find the count of multiples
           for (let i = 0; i < n; i++) {
               if (arr[i] % a == 0 && arr[i] % b == 0) {
                   bothAB++;
               }
               else if (arr[i] % a == 0) {
                   onlyA++;
               }
               else if (arr[i] % b == 0) {
                   onlyB++;
               }
           }
 
           if (onlyA + (bothAB > 0 ? 1 : 0) > onlyB) {
               return "Alice";
           }
           else {
               return "Bob";
           }
       }
 
       // Driver code
       let N = 6;
       let arr = [2, 4, 6, 3, 9, 12];
       let A = 2, B = 3;
 
       // Function call
       document.write(winner(arr, A, B, N));
 
      // This code is contributed by Potta Lokesh
 
   </script>

Output

Alice

Time Complexity: O(N)
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!