In this post, we will solve HackerRank Unfair Game Problem Solution.
You are playing a game of Nim with a friend. The rules are are follows:
1) Initially, there are N piles of stones. Two players play alternately.
2) In each turn, a player can choose one non empty pile and remove any number of stones from it. At least one stone must be removed.
3) The player who picks the last stone from the last non empty pile wins the game.
It is currently your friend’s turn. You suddenly realize that if your friend was to play optimally in that position, you would lose the game. So while he is not looking, you decide to cheat and add some (possibly 0) stones to each pile. You want the resultant position to be such that your friend has no guaranteed winning strategy, even if plays optimally. You cannot create a new pile of stones. You can only add stones, and not remove stones from a pile. What is the least number of stones you need to add?
Input Format
The first line contains the number of cases T. T cases follow. Each case contains the number N on the first line followed by N numbers on the second line. The ith number denotes si, the number of stones in the ith pile currently.
Constraints
1 <= T <= 20
2 <= N <= 15
1 <= si < 1000000000 (10^9)
Output Format
Output T lines, containing the answer for each case. If the current position is already losing for your friend, output 0.
Sample Input
3
2
1 3
3
1 1 1
4
10 4 5 1
Sample Output
2
3
6
Explanation
For the first case, add 2 stones to the first pile. Then, both piles will have 3 stones each. It is easy to verify that your friend cannot win the game unless you make a mistake.
For the second case, add 1 stone to the first pile, and 2 stones to the second pile.
Unfair Game C Solution
#include<stdio.h>
typedef long long i64;
int main()
{
int T;
scanf("%d", &T);
for (; T > 0; T--)
{
int n, i, j;
i64 result = 0;
int tmp, max, ind;
i64 s[16];
scanf("%d", &n);
for (i = 0; n > i; i++)
{
scanf("%d", s + i);
result += *(s + i);
}
while (1)
{
int bitcount[64]={0};
for (i = 31; i >= 0; i--)
{
int i0 = 0, i1;
for (j = 0; j < i; j++)
{
i0 <<= 1;
i0 += 1;
}
i1 = i0;
i1 <<= 1;
i1 += 1;
tmp = 0;
for (j = 0; j < n; j++)
{
tmp += ((s[j] >> i) & 1);
}
bitcount[i]=tmp;
if (tmp % 2 == 1 && tmp < n)
{
j = 0;
max = 0;
while (j < n)
{
if (((s[j] >> (i)) & 1) < 1 && (max <= (s[j] & i0)))
{
max = (s[j] & i0);
ind = j;
}
j++;
}
j = ind;
s[j] >>= i;
s[j] += 1;
s[j] <<= i;
break;
}
if (tmp%2==1&&tmp == n)
{
int k=0;
j = 0;
max = 0;
k=i+1;
while(bitcount[k]==n-1)k++;
i1=0;
for (j = 0; j < k; j++)
{
i1 <<= 1;
i1 += 1;
}
j=0;
while (j < n)
{
if (((s[j] >> (k)) & 1) < 1
&& (max <= (s[j] & i1)))
{
max = (s[j] & i1);
ind = j;
}
j++;
}
j = ind;
s[j] >>= (k);
s[j] += 1;
s[j] <<= (k);
break;
}
}
if (i < 0)
break;
}
for (i = 0; i < n; i++)
result -= s[i];
printf("%lld\n", -result);
}
return 0;
}
Unfair Game C++ Solution
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define REP(i,n) for(int (i)=0,_n=(n);(i)<_n;(i)++)
#define FOR(i,a,b) for(int (i)=(a),_n=(b);(i)<=_n;(i)++)
#define FORD(i,a,b) for(int (i)=(a),_n=(b);(i)>=_n;(i)--)
typedef long long LL;
const LL inf = 0x7ffffffffffffffLL;
int main()
{
int T;
scanf( "%d", &T );
while ( T-- ) {
int n;
LL ts[20];
scanf( "%d", &n );
REP(i,n) cin >> ts[i];
LL ans = inf;
REP(bit,1<<n) {
LL s[20];
REP(i,n) s[i] = ts[i];
LL tans = 0;
FORD(x,40,0) {
bool odd = false;
REP(i,n) if ( s[i] & (1LL << x) ) odd = !odd;
if ( !odd ) continue;
if ( __builtin_popcount(bit) <= 1 ) goto done;
int choose = 0;
LL cost = inf;
LL value = 1LL << x;
LL mask = value - 1;
REP(i,n) if ( (bit & (1 << i)) && !(s[i] & (1LL << x)) && value - (s[i] & mask) < cost )
cost = value - (s[i] & mask), choose = i;
if ( cost == inf ) {
do {
x++;
value = 1LL << x;
mask = value - 1;
REP(i,n) if ( (bit & (1 << i)) && !(s[i] & (1LL << x)) && value - (s[i] & mask) < cost )
cost = value - (s[i] & mask), choose = i;
if ( cost == inf ) continue;
s[choose] = (s[choose] & ~mask) | (1LL << x);
tans += cost;
break;
} while ( true );
x++;
}
else {
s[choose] = (s[choose] & ~mask) | (1LL << x);
tans += cost;
}
}
ans = min(ans,tans);
done:;
}
cout << ans << endl;
}
return 0;
}
Unfair Game C Sharp Solution
/* Sample program illustrating input/output */
using System;
using System.Collections;
using System.Linq;
using System.Diagnostics;
using System.Collections.Generic;
using System.IO;
class Solution {
static void Main(String[] args) {
int test;
test = Convert.ToInt32(Console.ReadLine());
for (int t = 0; t < test; t++)
{
int N;
N = Convert.ToInt32(Console.ReadLine());
int[] V = new int[N];
var bitArrays = new BitArray[N];
string numbers = Console.ReadLine();
string[] split = numbers.Split(new Char[] { ' ', '\t', '\n' });
int i = 0;
foreach (string s in split)
{
if (s.Trim() != "")
{
V[i] = Convert.ToInt32(s);
bitArrays[i] = new BitArray(new int[] { V[i] });
i++;
}
}
if (IsNimSumZero(bitArrays))
{
Console.WriteLine(0);
continue;
}
while (IsNimSumZero(bitArrays) == false)
{
var firstEmptyPlace = 32;
for (var bitPos = 31; bitPos >= 0; bitPos--)
{
var bitsCol = bitArrays.Select(b => b[bitPos]).ToList();
if (bitsCol.All(bit => bit == false)) continue;
if (firstEmptyPlace == 32)
firstEmptyPlace = bitPos + 1;
if (IsNimSumZero(bitsCol)) continue;
var maxValIdx = GetMaxElementIndex(bitArrays, bitPos);
// if all bits in column are TRUE
if (maxValIdx == -1)
{
maxValIdx = GetMaxElementIndex(bitArrays, firstEmptyPlace);
SetTrueFirstFalseOther(bitArrays[maxValIdx], firstEmptyPlace);
maxValIdx = GetMaxElementIndex(bitArrays, firstEmptyPlace);
SetTrueFirstFalseOther(bitArrays[maxValIdx], firstEmptyPlace);
break;
}
if (bitArrays[maxValIdx][bitPos]) throw new NotImplementedException("bitArrays[maxValIdx][bitPos] == true");
SetTrueFirstFalseOther(bitArrays[maxValIdx], bitPos);
}
}
var resArr = bitArrays.Select(ba => BitArrayToInt(ba)).ToArray();
int result = resArr.Zip(V, (res, orig) => res - orig).Sum();
Console.WriteLine(result);
}
}
private static void SetTrueFirstFalseOther(BitArray bitArray, int index)
{
bitArray[index] = true;
for (var pos = index - 1; pos >= 0; pos--)
bitArray[pos] = false;
}
private static int GetMaxElementIndex(BitArray[] src, int startPosition)
{
if (src == null || src.Length <= 1) throw new NotImplementedException();
if (src.All(ba => ba[startPosition])) return -1;
var dest = new BitArray[src.Length];
for (int pos = 0; pos < src.Length; pos++)
{
var newBits = new bool[32];
src[pos].CopyTo(newBits, 0);
if (newBits[startPosition] == true) continue;
//newBits = new bool[32];
for (int bitPos = 0; bitPos < 32; bitPos++)
if (bitPos > startPosition) newBits[bitPos] = false;
dest[pos] = new BitArray(newBits);
}
var maxIndex = dest
.Select((ba, i) => new { Index = i, Value = BitArrayToInt(ba) })
.OrderByDescending(item => item.Value)
.First().Index;
return maxIndex;
}
private static bool IsNimSumZero(BitArray[] values)
{
if (values == null || values.Length == 0) throw new ArgumentException("values");
var ints = values.Select(ba => BitArrayToInt(ba)).ToArray();
return IsNimSumZero(ints);
//var firstBitArr = values[0];
//for (var pos = 1; pos < values.Length; pos++)
// firstBitArr.Xor(values[pos]);
//var sum = BitArrayToInt(firstBitArr);
//Debug.WriteLine($"Sum: {sum}");
//return sum == 0;
}
private static int BitArrayToInt(BitArray bitArray)
{
if (bitArray == null)
return int.MinValue;
if (bitArray.Length > 32)
throw new ArgumentException("Argument length shall be at most 32 bits.");
int[] array = new int[1];
bitArray.CopyTo(array, 0);
return array[0];
}
private static bool IsNimSumZero(IEnumerable<bool> values)
{
if (values == null) throw new ArgumentException("values");
var nimSum = false;
foreach (var val in values)
nimSum ^= val;
return nimSum == false;
}
private static bool IsNimSumZero(int[] values)
{
if (values == null || values.Length == 0) throw new ArgumentException("values");
if (values.Length == 1)
if (values[0] == 0)
return true;
else
return false;
var nimSum = 0;
for (var pos = 0; pos < values.Length; pos++)
nimSum ^= values[pos];
//Debug.WriteLine($"Sum: {nimSum}");
return nimSum == 0;
}
}
Unfair Game Java Solution
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class UnfairGame {
static int om(int[] values, boolean notDone) {
int threshold = 0;
int stones = 0;
int nimSum = nimSum(values);
if (nimSum == 0)
return 0;
int index = getIndexOfLargest(values);
int t = values[index];
int digits = 0;
while (t != 0) {
t >>= 1;
digits++;
}
int[] newValues = values.clone();
newValues[index] = 1 << digits;
int buffer = newValues[index] - values[index];
while (nimSum != 0) {
int highestBit = -1;
while (nimSum != 0) {
nimSum >>= 1;
highestBit++;
}
int required = 1 << highestBit;
threshold = required << 1;
int mask = required - 1;
int least = required;
int keyIndex = -1;
int standby = -1;
int atleast = required;
for (int i = 0; i < values.length; i++) {
int offer = required - (values[i] & mask);
if (offer <= atleast) {
atleast = offer;
standby = i;
}
if (offer <= least && (offer + (values[i] & (threshold - 1))) < threshold
&& (values[i] & required) == 0) {
least = offer;
keyIndex = i;
}
}
if (keyIndex == -1) {
stones += atleast;
values[standby] += atleast;
} else {
stones += least;
values[keyIndex] += least;
}
nimSum = nimSum(values);
}
if (stones < threshold || !notDone) {
return stones;
}
int chance = om(newValues, false);
if (buffer + chance < stones)
return buffer + chance;
else
return stones;
}
static int nimSum(int[] values) {
int sum = 0;
for (int i = 0; i < values.length; i++) {
sum ^= values[i];
}
return sum;
}
static int getIndexOfLargest(int[] values) {
int mask = 1 << 31;
mask--;
return getIndexOfLargest(mask, values);
}
static int getIndexOfLargest(int mask, int[] values) {
int largestIndex = 0;
for (int i = 0; i < values.length; i++) {
if ((values[i] & mask) > values[largestIndex])
largestIndex = i;
}
return largestIndex;
}
static int pairs(int[] values, int bitIndex) {
int count = 0;
int v = 1 << bitIndex;
for (int i = 0; i < values.length; i++) {
if ((values[i] & v) > 0)
count++;
}
return count;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
int T = Integer.parseInt(s);
for (int i = 0; i < T; i++) {
s = br.readLine();
int N = Integer.parseInt(s);
s = br.readLine();
String[] ss = s.split("\\s");
int[] values = new int[N];
for (int j = 0; j < N; j++) {
values[j] = Integer.parseInt(ss[j]);
}
System.out.println(om(values,true));
}
}
}
Unfair Game JavaScript Solution
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.trim().split('\n').map(str => str.trim());
main();
});
function readLine() {
return inputString[currentLine++];
}
/*
* Complete the unfairGame function below.
*/
function unfairGame(s) {
/*
* Write your code here.
*/
let sum = 0;
let xor = s.reduce((prev, cur) => prev ^ cur);
let msb = findMSB(xor);
let curBit = s.reduce((prev, cur) => cur & (prev & msb));
if (curBit) {
let poss = {};
let cheap = 0;
s.forEach((n, idx) => {
let next = n + msb;
let nextBit = (n ^ next) & next;
if (poss[nextBit] == null) {
poss[nextBit] = [];
cheap--;
}
cheap++;
poss[nextBit].push({
cost: (next & ~(nextBit - 1)) - n,
idx,
});
});
while (!cheap) {
// now have to figure out the hard cost of moving each one to their left
// for each key, add all the subkeys that are smaller and compatible
let sorted = Object.keys(poss).sort((a, b) => a - b);
let maxIdx = Object.keys(poss).length - 1;
let max = sorted[maxIdx];
let min = sorted[0];
//console.log(min, max, maxIdx);
console.log(poss);
for (let key = min; key - max < 0; key <<= 1) {
//console.log(poss[key], key);
poss[key].forEach(el => {
//console.log(el);
let nKey = key << 1;
let n = s[el.idx];
let next = n + nKey;
let nextBit = (n ^ next) & next;
if (poss[nextBit] == null) {
poss[nextBit] = [];
cheap--;
}
cheap++;
let updated = 0;
poss[nextBit].forEach((el2, idx) => {
if (el2.idx === el.idx) {
updated = 1;
poss[nextBit][idx] = {
cost: Math.min((next & ~(nextBit - 1)) - n, el2.cost),
idx: el.idx,
}
}
});
if (!updated) {
poss[nextBit].push({
cost: (next & ~(nextBit - 1)) - n,
idx: el.idx,
});
}
});
}
//console.log(poss);
}
for (const [key, value] of Object.entries(poss)) {
if (poss[key].length < 2) {
delete poss[key];
}
}
// for each poss, find the cheapest pair, and then find cheapest poss
let min = -1;
let minKey = -1;
for (const [key, value] of Object.entries(poss)) {
poss[key].sort((a, b) => a.cost - b.cost);
let cost = poss[key][0].cost + poss[key][1].cost;
if (min === -1 || cost < min) {
min = cost;
minKey = key;
}
}
// update the cheapest pair to new value, update xor and sum
xor ^= s[poss[minKey][0].idx];
xor ^= s[poss[minKey][1].idx];
sum += min;
s[poss[minKey][0].idx] = minKey;
s[poss[minKey][1].idx] = minKey;
}
while (xor) {
msb = findMSB(xor);
// clear all bits of elements of s bigger than msb
let mask = ((msb - 1) << 1) + 1;
s = s.map(n => n & mask);
// find the element of s w/ 0 on msb w/ least cost to upgrade to 1
let min = msb + 1;
let minIdx = -1;
s.forEach((n, idx) => {
if (n & msb) {
return;
}
let cost = msb - n;
if (cost < min) {
min = cost;
minIdx = idx;
}
});
// upgrade the one w/ least cost, updating sum and xor
xor ^= s[minIdx];
xor ^= msb;
sum += min
s[minIdx] = msb;
}
return sum;
}
function findMSB(n) {
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n = n + 1;
return (n >> 1);
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const t = parseInt(readLine(), 10);
for (let tItr = 0; tItr < t; tItr++) {
const sCount = parseInt(readLine(), 10);
const s = readLine().split(' ').map(sTemp => parseInt(sTemp, 10));
let result = unfairGame(s);
ws.write(result + "\n");
}
ws.end();
}
Unfair Game Python Solution
#!/bin/python3
import operator
from functools import reduce
def xor(nums):
return reduce(operator.xor, nums, 0)
def lowZero(v):
"""position of the lowest 0"""
p = 0
while True:
m = 1 << p
if v & m == 0:
return p
p += 1
def highOne(v):
"""position of the highest 1"""
p = 0
high = None
while v != 0:
m = 1 << p
if v & m != 0:
high = p
v &= ~m
p += 1
return high
def zeroAt(v, p):
"""true if v has 0 at position p"""
return v & (1 << p) == 0
def diffToFlip(v, p):
"""how much to add to flip the bit at p and clear below it"""
t = 1 << p
r = (v + t) & ~(t - 1)
return r - v
def lowPosWithMoreThanOneZero(nums):
"""lowest position where more than one number has 0"""
p = 0
while True:
m = 1 << p
n = sum(1 if v & m == 0 else 0 for v in nums)
if n > 1:
return p
p += 1
def pairs(n):
return ((i, j) for i in range(0, n - 1) for j in range(i + 1, n))
"""pile fixers"""
def fixPiles(piles):
"""add minimum number of counters to piles to make them a staple nim position"""
highOneP = highOne(xor(piles))
if highOneP == None: # the piles are in a winning position
r = piles
elif any(zeroAt(v, highOneP) for v in piles):
r = fixPilesWithZeroAtHigh(piles)
else:
r = fixPilesWithoutZeroAtHigh(piles, highOneP)
return r
def fixPilesWithZeroAtHigh(piles):
"""fix piles that have a pile with zero at the high 1-bit position"""
piles = list(piles)
while True:
highOneP = highOne(xor(piles))
"""see if the piles are fixed to a winning position"""
if highOneP == None:
return piles
"""choose a pile with 0 at the high 1 position with min to add to flip that 0"""
candidates = [(i, diffToFlip(v, highOneP)) for i, v in enumerate(piles) if zeroAt(v, highOneP)]
winner = min(candidates, key = operator.itemgetter(1))
"""add to the winning pile"""
i, add = winner
piles[i] += add
return piles
def fixPilesWithoutZeroAtHigh(piles, highOneP):
"""fix piles that do not have a pile with zero at the high 1-bit position"""
"""high piles are piles' bits above highOneP"""
highPiles = [v >> (highOneP + 1) for v in piles]
"""decorate each high pile the position of the first 0, same as the number
of trailing ones"""
highPilesZ = [(v, lowZero(v)) for v in highPiles]
"""find pairs with matching trailing ones; each match is a 3-tuple of two pile
indices and the position of the zero"""
matches = [(i, j, highOneP + 1 + highPilesZ[i][1]) for i, j in pairs(len(piles)) if highPilesZ[i][1] == highPilesZ[j][1]]
"""if there are pairs with matching trailing ones find the lowest position with
at least two zeros; each pair of piles in this set is a matching pair"""
if not matches:
zeroP = lowPosWithMoreThanOneZero(highPiles)
lowzs = [i for i, v in enumerate(highPiles) if zeroAt(v, zeroP)]
nz = len(lowzs)
baseZeroP = highOneP + 1 + zeroP
matches = [(lowzs[i], lowzs[j], baseZeroP) for i, j in pairs(nz)]
"""for each pair add to flip the matching zeros and fix resulting piles with the
zero-at-high-1 fixer; then choose the best result out of all pairs"""
results = (fixPilesTwoZeros(piles, zeroP, i, j) for i, j, zeroP in matches)
return min(results, key = sum)
def fixPilesTwoZeros(piles, zeroP, i, j):
"""given a set of piles where piles i, j have zeros at zeroP add to each pile to flip that zero and
then fix the piles"""
iAdd = diffToFlip(piles[i], zeroP)
jAdd = diffToFlip(piles[j], zeroP)
piles = list(piles)
piles[i] += iAdd
piles[j] += jAdd
return fixPilesWithZeroAtHigh(piles)
def solve(piles):
fixedPiles = fixPiles(piles)
return sum(fixedPiles) - sum(piles), fixedPiles
def readLine(): return input()
def readInt(): return int(readLine())
def readInts(): return tuple(int(token) for token in readLine().split())
def readIntList(): return list(readInts())
def main():
nt = readInt()
for _ in range(nt):
_n = readInt()
piles = readIntList()
answer, _fixedPiles = solve(piles)
print(answer)
main()