Winner in Array Transformation Game with Permutation Goal

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.

Recommended: Selection Sort

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.