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(N2)
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.
- Check if arr[i] is multiple of both A and B.
- 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 winnerstring 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 codeint 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 approachclass 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 winnerdef 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 codeN = 6arr = [2, 4, 6, 3, 9, 12]A,B = 2,3# Function callprint(winner(arr, A, B, N))# This code is contributed by shinjanpatra |
C#
// c# code to implement the approachusing 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> |
Alice
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
