Find Winner by emptying the Array by Sum Modulo Array element
Given an array Arr[] of size N, two players A and B are playing a game on this array by taking turns and A makes the first move. On each move, they can perform the following operation on the array:
- Choose a number Arr[i]
- add the (Sum of array % Arr[i]) to their score
- then remove that number from the array.
- After removal, the length of the array is reduced by 1.
The game continues until the array becomes empty, and the player with the highest score wins the game. Your task is to determine the winner of the game or determine if the game ends with a draw.
Constraints:
1 <= N <= 20
1 <= Arr[i] <=10^9
Example:
Input: N=3, Arr=[3, 4, 5]
Output: Player B wins
Explanation:
In first move Arr=[3, 4, 5], Player A takes 5 and get score = 12 % 5 = 2
In second move Arr=[3, 4], Player B takes 4 and get score = 7 % 4 = 3
In third move Arr=[3], Player A takes 3 and get score = 3 % 3 = 0
Total score of Player B is greater than that of Player A, so winner = BInput: N=5, Arr=[3, 1, 2, 4, 5]
Output: Player A wins
Explanation:
In the first move, Arr[] = [3, 1, 2, 4, 5], A takes 4 and gets score = 15 % 4 = 3
In the second move, Arr[] = [3, 1, 2, 5], B takes 3 and get score = 11 % 3 = 2
In the third move, Arr[] = [1, 2, 5], A takes 5 and gets score = 8 % 5 = 3
In the fourth move, Arr[] = [1, 2], B takes 2 and gets score = 3 % 2 = 1
In the fifth move, Arr[] = [1], A takes 1 and gets score = 1 % 1 = 0
Total score of Player A is higher than that of Player B, so winner = AInput: N=4, Arr=[1, 1, 2, 2]
Output: Draw
Explanation: After the game ends both the players will have a final score of 0.
Approach: The problem can be solved using the following approach:
The problem can be solved using Dynamic Programming and Bit Manipulation. We can create bitmasks for all possible distributions of array element where if the ith bit is set, it indicates that the ith array element has already been used. When the mask has even number of set bits, it means Player A has to make a move while if the mask has odd number of set bits, then Player B makes a move.
Each player tries to maximize the score, Let the current bitmask has X set bits, then following condition is followed for this bitmask to be a winning, loosing, or draw state:
- Bitmask(X set bits) is Winning: If (Maximum score of bitmask with X set bits – Maximum score of bitmasks with X+1 set bits) is positive.
- Bitmask(X set bits) is Loosing: If (Maximum score of bitmask with X set bits – Maximum score of bitmasks with X+1 set bits) is negative.
- Bitmask(X set bits) is Draw: If (Maximum score of bitmask with X set bits – Maximum score of bitmasks with X+1 set bits) is 0.
Conclusion: The final result depends upon the maximum cumulative difference at bitmask = 0 where Player A makes the first move:
- If maximum cumulative difference of bitmask (0) > 0: Player A wins
- If maximum cumulative difference of bitmask (0) < 0: Player B wins
- If maximum cumulative difference of bitmask (0) = 0: Draw
Let us understand this using an example where Arr[] = {3, 4, 5}, the below image shows all the possible bitmask states for player A and B
Since the answer depends upon the final maximum cumulative difference for bitmask 0 based upon above mentioned formula i.e. maximum value of Xth bit – maximum value of (X+1)th bit. All possible values for bitmask 0 are listed below:
- 2 – (max(3, 1) – (max(0, 0))) = -1
- 0 – (max(3, 2) – (max(0, 0)))= -3
- 0 – (max(4, 1) – (max(0, 0))) = -4
Maximum cumulative sum for bitmask(0) = max(-1, -3, -4) = -1, which is negative, so Player B wins the game.
Steps to solve the problem:
- Define a function, say winnerOfGame(mask) which takes the current mask as input and returns the maximum sum possible with the current mask.
- Iterate over all the unset bits and for every bit which is 0, change it to 1 to get the new mask and call the recursive function winnerOfGame(new mask) with the new mask.
- After iterating over all the possible new masks, return the maximum sum possible.
- Return the result as winnerOfGame(mask), with initial mask as 0.
Below is the implementation of above approach:
C++
#include <bits/stdc++.h> using namespace std; int winnerOfGame( int mask, int sum, vector< int >& arr, map< int , int >& dp) { // if mask is already computed simply return it if (dp.count(mask)) return dp[mask]; // if all the elments are taken return 0 if (__builtin_popcount(mask) == arr.size()) return 0; // since we want to return maximum value, initialize the // result as negative infinity int result = -1e9; int n = arr.size(); // iterate on each array element for ( int i = 0; i < n; i++) { // if i'th bit is not set we can take it if (((mask >> i) & 1) == 0) { // create a new mask by making i'th bit set int new_mask = (mask | (1 << i)); // storing maximum possible value of the mask // in result result = max(result, sum % arr[i] - winnerOfGame(new_mask, sum - arr[i], arr, dp)); } } return dp[mask] = result; } // Driver Function int main() { // input array vector< int > Arr = { 3, 4, 5 }; // initial sum of array elements int sum = accumulate(Arr.begin(), Arr.end(), 0); // dp to cache bitmasks to its maximum value map< int , int > dp; // function call to get result = {positive, negative, 0} int result = winnerOfGame(0, sum, Arr, dp); // if result is 0 its a draw if (result == 0) { cout << "Draw"; } // if result is positive player A wins else if (result > 0) { cout << "Player A wins"; } // if result is negative player B wins else { cout << "Player B wins"; } cout << endl; } |
Java
// Java code to implement the above approach import java.util.*; class Main { static int winnerOfGame( int mask, int sum, ArrayList<Integer> arr, HashMap<Integer, Integer> dp) { // if mask is already computed simply return it if (dp.containsKey(mask)) return dp.get(mask); // if all the elements are taken return 0 if (Integer.bitCount(mask) == arr.size()) return 0 ; // since we want to return the maximum value, // initialize the result as negative infinity int result = Integer.MIN_VALUE; int n = arr.size(); // iterate on each array element for ( int i = 0 ; i < n; i++) { // if i'th bit is not set we can take it if (((mask >> i) & 1 ) == 0 ) { // create a new mask by making i'th bit set int newMask = (mask | ( 1 << i)); // storing the maximum possible value of the // mask in result result = Math.max( result, sum % arr.get(i) - winnerOfGame(newMask, sum - arr.get(i), arr, dp)); } } dp.put(mask, result); return result; } // Driver Function public static void main(String[] args) { // input array ArrayList<Integer> arr = new ArrayList<>(Arrays.asList( 3 , 4 , 5 )); // initial sum of array elements int sum = arr.stream() .mapToInt(Integer::intValue) .sum(); // dp to cache bitmasks to their maximum value HashMap<Integer, Integer> dp = new HashMap<>(); // function call to get the result = {positive, // negative, 0} int result = winnerOfGame( 0 , sum, arr, dp); // if the result is 0, it's a draw if (result == 0 ) { System.out.println( "Draw" ); } // if the result is positive, Player A wins else if (result > 0 ) { System.out.println( "Player A wins" ); } // if the result is negative, Player B wins else { System.out.println( "Player B wins" ); } } } // This code is contributed by Abhinav Mahajan (abhinav_m22) |
Python3
def winner_of_game(mask, sum_val, arr, dp): # If the result for the current mask is already computed, return it if mask in dp: return dp[mask] # If all elements are taken, return 0 (draw) if bin (mask).count( '1' ) = = len (arr): return 0 # Initialize result to a large negative value result = - 1e9 n = len (arr) # Iterate on each array element for i in range (n): # If i'th bit is not set, we can take it if ((mask >> i) & 1 ) = = 0 : # Create a new mask by making i'th bit set new_mask = mask | ( 1 << i) # Store the maximum possible value of the mask in the result result = max (result, sum_val % arr[i] - winner_of_game(new_mask, sum_val - arr[i], arr, dp)) # Memoize the result for the current mask dp[mask] = result return result # Driver Code if __name__ = = "__main__" : Arr = [ 3 , 4 , 5 ] # Initial sum of array elements sum_val = sum (Arr) # Dictionary to cache bitmasks to their maximum value dp = {} # Function call to get result = {positive, negative, 0} result = winner_of_game( 0 , sum_val, Arr, dp) if result = = 0 : print ( "Draw" ) elif result > 0 : print ( "Player A wins" ) else : print ( "Player B wins" ) |
C#
using System; using System.Collections.Generic; using System.Linq; class Program { static int WinnerOfGame( int mask, int sum, List< int > arr, Dictionary< int , int > dp) { // If mask is already computed, return it if (dp.ContainsKey(mask)) return dp[mask]; // If all the elements are taken, return 0 if (BitCount(mask) == arr.Count) return 0; // Initialize the result as negative infinity since we want to return the maximum value int result = int .MinValue; int n = arr.Count; // Iterate on each array element for ( int i = 0; i < n; i++) { // If i'th bit is not set, we can take it if (((mask >> i) & 1) == 0) { // Create a new mask by making i'th bit set int newMask = (mask | (1 << i)); // Store the maximum possible value of the mask in result result = Math.Max(result, sum % arr[i] - WinnerOfGame(newMask, sum - arr[i], arr, dp)); } } return dp[mask] = result; } // Helper function to count set bits (1s) in an integer static int BitCount( int n) { int count = 0; while (n > 0) { count += n & 1; n >>= 1; } return count; } static void Main() { // Input array List< int > arr = new List< int > { 3, 4, 5 }; // Initial sum of array elements int sum = arr.Sum(); // Dictionary to cache bitmasks to their maximum value Dictionary< int , int > dp = new Dictionary< int , int >(); // Function call to get result = {positive, negative, 0} int result = WinnerOfGame(0, sum, arr, dp); // Output based on the result if (result == 0) { Console.WriteLine( "Draw" ); } else if (result > 0) { Console.WriteLine( "Player A wins" ); } else { Console.WriteLine( "Player B wins" ); } } } |
Javascript
function GFG(mask, sum, arr, dp) { // If mask is already computed, simply return it if (dp.has(mask)) { return dp.get(mask); } // If all the elements are taken, return 0 if (countBits(mask) === arr.length) { return 0; } // Since we want to return the maximum value // initialize the result as negative infinity let result = -1e9; const n = arr.length; // Iterate on each array element for (let i = 0; i < n; i++) { if (((mask >> i) & 1) === 0) { const newMask = mask | (1 << i); // Store the maximum possible value of the mask in result result = Math.max(result, sum % arr[i] - GFG(newMask, sum - arr[i], arr, dp)); } } // Cache the result for the current mask dp.set(mask, result); return result; } // Helper function to count the number of the set bits in a number function countBits(num) { let count = 0; while (num) { count += num & 1; num >>= 1; } return count; } // Driver Function function main() { // Input array const arr = [3, 4, 5]; // Initial sum of array elements const sum = arr.reduce((acc, curr) => acc + curr, 0); const dp = new Map(); const result = GFG(0, sum, arr, dp); // Output the result if (result === 0) { console.log( "Draw" ); } else if (result > 0) { console.log( "Player A wins" ); } else { console.log( "Player B wins" ); } } main(); |
Player_B wins
Time complexity: O(N*(2^N)), where N is the size of the input array Arr[]
Auxiliary Space: O(2^N)