Given an array of integers, A[] of size n with elements in range 1 to n may not consist of all the numbers from 1 to n. There are two players P1 and P2, who play in alternate turns in each turn a player can choose any index i and increase only A[i] by 1 only once in the array on each turn. But the condition is if the player who can make the array into a permutation of integers from 1 to n finally wins. Starting with player P1. If P1 can’t make any change then P2 wins.
Examples:
Input: 1 1 1 1 1 Output: P2 Explanation: Always P1 starts, P1 can increase by 1 at 2nd index 1 2 1 1 1 P2's turn: P2 can increse by 1 at 3rd index 1 2 2 1 1 P1 can increase by 1 at 3rd index 1 2 3 1 1 P2 can increase by 1 at 4rd index 1 2 3 2 1 P1 can increase by 1 at 4th index 1 2 3 3 1 P2 can increase by 1 at 4th index 1 2 3 4 1 P1 can increase by 1 at 5th index 1 2 3 4 2 P2 can increase by 1 at 5th index 1 2 3 4 3 P1 can increase by 1 at 5th index 1 2 3 4 4 P2 can increase by 1 at 5th index 1 2 3 4 5 P2 has obtained the permutation of integers from 1 to n so P1 can't make any addition so P2 wins. Input: 1 2 2 3 5 Output: P2 P1 starts and increase at 2nd index by 1 so array becomes 1 2 3 3 5 on P2's turn it changes to 1 2 3 4 5 and P1 can't make any change since it is a permutation of 1 to n so P2 wins. Input: 2 2 3 Output: P2 Since P1 can't make any addition.
Approach:
This approach is based on sorting.
Follow these steps to solve this problem.
- First, sort the given array A[].
- Then create another array B[] with its elements as 1 to n and declare a variable added in main initialized to 0.
- Sorting is used in order to compare numbers from 1 to n in array B[].
- Traverse the arrays and check for the difference between B[i] and A[i] if it is negative at any index then P1 can’t make any addition so P2 wins.
- If the difference between B[i] and A[i] is not negative then keep track of the difference and add it to variable to_be_added.
- If the to_be_added is even both P1 and P2 have equally played and the final addition is made by P2 so P2 wins.
- If the to_be_added is odd then the final addition is made by P1 so P1 wins.
Implementation:
C
// C implementation for the above approach #include <stdio.h> // A utility function to swap two elements void swap(int * p, int * q) { int t = * p; * p = * q; * q = t; } // QUICK SORT int partition(int a[], int first, int last) { int pivot = a[last]; int i = (first - 1); for (int j = first; j <= last - 1; j++) { if (a[j] < pivot) { i++; swap( & a[i], & a[j]); } } swap( & a[i + 1], & a[last]); return (i + 1); } void Sort(int a[], int l, int h) { if (l < h) { int p = partition(a, l, h); Sort(a, l, p - 1); Sort(a, p + 1, h); } } // Function to find the winner int findWinner(int a[], int n) { // declaring another array b with 1 to n int i, b[n]; for (i = 0; i < n; i++) { b[i] = i + 1; } Sort(a, 0, n); int to_be_added = 0; for (i = 0; i < n; i++) { // checking for the if the difference is negative // means some integer in b is exceeding the range // between 1 to n so P1 cant add if (b[i] - a[i] < 0) { return 0; } if (b[i] - a[i] > 0) { // keeping track of difference to find find who // made the last addition to_be_added = to_be_added + (b[i] - a[i]); } } return to_be_added; } // Utility function to check the winner void checkWinner(int added) { if (added == 0) { // P1 couldn't make any addition printf("P2 wins\n"); } else if (added % 2 == 1) { // last addition made by P1 printf("P1 wins\n"); } else if (added % 2 == 0) { // last addition made by P2 printf("P2 wins\n"); } } int main() { int i, n; int A[] = { 1, 1, 1, 1, 1 }; n = sizeof(A) / sizeof(A[0]); int added = findWinner(A, n); // Check the winner checkWinner(added); return 0; }
C++
// C++ implementation for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the winner int findWinner(int a[], int n) { // declaring another array b with 1 to n int i, b[n]; for (i = 0; i < n; i++) { b[i] = i + 1; } sort(a, a + n); int to_be_added = 0; for (i = 0; i < n; i++) { // checking for the if the difference is negative // means some integer in b is exceeding the range // between 1 to n so P1 cant add */ if (b[i] - a[i] < 0) { return 0; } if (b[i] - a[i] > 0) { // keeping track of difference to find find who // made the last addition to_be_added = to_be_added + (b[i] - a[i]); } } return to_be_added; } // Utility function to check the winner void checkWinner(int added) { if (added == 0) { // P1 couldn't make any addition cout << "P2 wins" << endl; } else if (added % 2 == 1) { // last addition made by P1 cout << "P1 wins" << endl; } else if (added % 2 == 0) { // last addition made by P2 cout << "P2 wins" << endl; } } int main() { int i, n; int A[] = { 1, 1, 1, 1, 1 }; n = sizeof(A) / sizeof(A[0]); int added = findWinner(A, n); // Check the winner checkWinner(added); return 0; }
Output:
P2 wins
Time Complexity: O(nlogn), where n is the number of elements in the array.
Auxiliary Space: O(n)
Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.