Given an array arr[] consisting of N integers. Two players, Player 1 and Player 2, play turn-by-turn in which one player can may either of the following two moves:
- Convert even array element to any other integer.
- Remove odd array element.
The player who is not able to make any move loses the game. The task is to print the winner of the game. Print -1 if the game may go on forever.
Examples:
Input: arr[] = {3, 1, 9, 7}
Output: Player 2
Explanation: Since all array elements are odd, no conversion is possible.
Turn 1: Player 1 deletes 3.
Turn 2: Player 2 deletes 1.
Turn 3: Player 1 deletes 9.
Turn 4: Player 2 deletes 7. Now, Player 1 has no moves left. Therefore, Player 2 wins the game.Input: arr[]={4, 8}
Output: -1
Approach: Follow the steps below to solve the problem:
- Traverse the array.
- Count the number of even and odd elements present in the array.
- If the number of even elements is zero, perform the following operations:
- If the count of odd is even, then Player 2 will win the game.
- Otherwise, Player 1 will win the game.
- If the count of odd is odd and only one even element is present in the array, then Player 1 will win the game.
- Otherwise, there will be a draw every time.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to evaluate the// winner of the gamevoid findWinner(int arr[], int N){ // Stores count of odd // array elements int odd = 0; // Stores count of even // array elements int even = 0; // Traverse the array for (int i = 0; i < N; i++) { // If array element is odd if (arr[i] % 2 == 1) { odd++; } // Otherwise else { even++; } } // If count of even is zero if (even == 0) { // If count of odd is even if (odd % 2 == 0) { cout << "Player 2" << endl; } // If count of odd is odd else if (odd % 2 == 1) { cout << "Player 1" << endl; } } // If count of odd is odd and // count of even is one else if (even == 1 && odd % 2 == 1) { cout << "Player 1" << endl; } // Otherwise else { cout << -1 << endl; }}// Driver Codeint main(){ int arr[] = { 3, 1, 9, 7 }; int N = sizeof(arr) / sizeof(arr[0]); findWinner(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to evaluate the// winner of the gamestatic void findWinner(int arr[], int N){ // Stores count of odd // array elements int odd = 0; // Stores count of even // array elements int even = 0; // Traverse the array for(int i = 0; i < N; i++) { // If array element is odd if (arr[i] % 2 == 1) { odd++; } // Otherwise else { even++; } } // If count of even is zero if (even == 0) { // If count of odd is even if (odd % 2 == 0) { System.out.println("Player 2"); } // If count of odd is odd else if (odd % 2 == 1) { System.out.println("Player 1"); } } // If count of odd is odd and // count of even is one else if (even == 1 && odd % 2 == 1) { System.out.println("Player 1"); } // Otherwise else { System.out.println(-1); }}// Driver Codepublic static void main(String args[]){ int arr[] = { 3, 1, 9, 7 }; int N = arr.length; findWinner(arr, N);}}// This code is contributed by ipg2016107 |
Python3
# Python3 program for the above approach # Function to evaluate the # winner of the gamedef findWinner(arr, N): # Stores count of odd # array elements odd = 0 # Stores count of even # array elements even = 0 # Traverse the array for i in range(N): # If array element is odd if (arr[i] % 2 == 1): odd += 1 # Otherwise else: even += 1 # If count of even is zero if (even == 0): # If count of odd is even if (odd % 2 == 0): print("Player 2") # If count of odd is odd elif (odd % 2 == 1): print("Player 1") # If count of odd is odd and # count of even is one elif (even == 1 and odd % 2 == 1): print("Player 1") # Otherwise else: print(-1)# Driver codeif __name__ == '__main__': arr = [ 3, 1, 9, 7 ] N = len(arr) findWinner(arr, N)# This code is contributed by Shivam Singh |
C#
// C# program for the above approachusing System;class GFG{ // Function to evaluate the// winner of the gamestatic void findWinner(int []arr, int N){ // Stores count of odd // array elements int odd = 0; // Stores count of even // array elements int even = 0; // Traverse the array for(int i = 0; i < N; i++) { // If array element is odd if (arr[i] % 2 == 1) { odd++; } // Otherwise else { even++; } } // If count of even is zero if (even == 0) { // If count of odd is even if (odd % 2 == 0) { Console.WriteLine("Player 2"); } // If count of odd is odd else if (odd % 2 == 1) { Console.WriteLine("Player 1"); } } // If count of odd is odd and // count of even is one else if (even == 1 && odd % 2 == 1) { Console.WriteLine("Player 1"); } // Otherwise else { Console.WriteLine(-1); }}// Driver Codepublic static void Main(){ int []arr = { 3, 1, 9, 7 }; int N = arr.Length; findWinner(arr, N);}}// This code is contributed by bgangwar59 |
Javascript
<script>// JavaScript program to implement// the above approach// Function to evaluate the// winner of the gamefunction findWinner(arr, N){ // Stores count of odd // array elements let odd = 0; // Stores count of even // array elements let even = 0; // Traverse the array for(let i = 0; i < N; i++) { // If array element is odd if (arr[i] % 2 == 1) { odd++; } // Otherwise else { even++; } } // If count of even is zero if (even == 0) { // If count of odd is even if (odd % 2 == 0) { document.write("Player 2"); } // If count of odd is odd else if (odd % 2 == 1) { document.write("Player 1"); } } // If count of odd is odd and // count of even is one else if (even == 1 && odd % 2 == 1) { document.write("Player 1"); } // Otherwise else { document.write(-1); }}// Driver Code let arr = [ 3, 1, 9, 7 ]; let N = arr.length; findWinner(arr, N); </script> |
Output:
Player 2
Time Complexity: O(N)
Auxiliary Space: O(1)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!