Table of Contents
Unfair Game – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ replace HackerRank 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;
}
Java rep HackerRank Solution
import java.util.*;
import java.io.*;
import static java.lang.Math.*;
public class Solution {
static class Foo57 {
static final long INF = Long.MAX_VALUE/3;
void main() {
BufferedReader br = null;
try {
br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine().trim());
for (int i = 0; i < T; i++) {
int N = Integer.parseInt(br.readLine().trim());
int[] arr = new int[N];
String[] s = br.readLine().trim().split("\\s+");
for (int j = 0; j < N; j++) {
arr[j] = Integer.parseInt(s[j].trim());
}
long res = foo(arr);
System.out.println(res);
}
} catch (Exception e) {
e.printStackTrace();
} finally {
if (br != null) {
try { br.close(); } catch (Exception e) { e.printStackTrace(); }
}
}
}
long foo(int[] arr) {
int N = arr.length;
int MAX = 29;
while (MAX >= 0) {
boolean find = false;
for (int val : arr)
if ((val & 1<<MAX) != 0) {
find = true;
break;
}
if (find) break;
MAX--;
}
MAX += 3;
int[] vec = new int[MAX];
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < N; j++) {
if ((arr[j] & 1<<i) != 0)
vec[i] |= 1<<j;
}
}
int MOD = (1<<N)-1;
long[][] dp = new long[MAX][1<<N];
for (long[] a : dp) Arrays.fill(a, INF);
Arrays.fill(dp[0], 0);
for (int i = 1; i < MAX; i++) {
for (int state = 0; state < (1<<N); state++) {
int bit = i-1;
int v = Integer.bitCount(~state&vec[bit]&MOD)&1;
//int v = 0;
long add = -(long)Integer.bitCount(state&vec[bit]&MOD) << bit;
//long add = 0;
/*for (int j = 0; j < N; j++) {
if ((state & 1<<j ) == 0 && (arr[j] & 1<<bit) != 0) {
v ^= 1;
} else if ((state & 1<<j) != 0 && (arr[j] & 1<<bit) != 0) {
add -= 1<<bit;
}
}*/
if (v == 0) {
dp[i][state] = min(dp[i][state], dp[i-1][state] + add);
} else {
// find one to toggle
int curr = MOD - (~state&vec[bit]&MOD);
long toAdd = add + (1<<bit);
while (curr > 0) {
int a = curr-1;
dp[i][state] = min(dp[i][state], dp[i-1][state|(~a&curr)] + toAdd);
curr &= a;
}
/*for (int j = 0; j < N; j++) {
if ((curr & 1<<j) != 0) {
dp[i][state] = min(dp[i][state], dp[i-1][state|1<<j] + toAdd);
}
}*/
}
// when state == 0 and no need to toggle, try to find 2 zero to toggle
if (state == 0 && v == 0) {
for (int j = 0; j < N; j++) {
if ((arr[j] & 1<<bit) != 0) continue;
for (int k = j+1; k < N; k++) {
if ((arr[k] & 1<<bit) != 0) continue;
dp[i][state] = min(dp[i][state], dp[i-1][state|1<<j|1<<k] + (1L<<bit+1));
}
}
}
}
}
return dp[MAX-1][0];
}
}
public static void main(String[] args) {
Foo57 foo = new Foo57();
foo.main();
}
}
Python 3 rep HackerRank Solution
#!/bin/python3
import os
import sys
#
# Complete the unfairGame function below.
#
def unfairGame(s):
nimSum = 0
for i in s:
nimSum ^= int(i)
if(nimSum == 0):
return 0
# if(nimSum == 1):
# modlist = [x % 2 for x in s]
# if min(modlist) == 0:
# s[modlist.index(0)] += 1
# else:
# s[0] += 1
# return 1 + unfairGame(s)
print(s)
divider = 2 ** (len(bin(nimSum)) - 3)
print(divider)
modlist = [x % divider if x % (2 * divider) < divider else -1 for x in s]
print(modlist)
if max(modlist) < 0:
s[s.index(max(s))] += divider
return divider + unfairGame(s)
increaseNumber = max(modlist)
increase = divider - increaseNumber
print(increase)
s[modlist.index(increaseNumber)] += increase
print(s)
print()
return increase + unfairGame(s)
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
t = int(input())
nums =[1, 10, 10, 15, 27, 4, 9, 12, 26, 9, 14, 3, 25, 23, 3, 10, 3, 5, 13, 18]
for i in nums:
print(i)
for t_itr in range(t):
s_count = int(input())
s = list(map(int, input().rstrip().split()))
s.sort()
result = unfairGame(s)
fptr.write(str(result) + '\n')
fptr.close()
Python 2 rep HackerRank Solution
'''
Unfair Game (40)
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:
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 p_i, the number of stones in the ith pile
currently.
Output:
Output T lines, containing the answer for each case. If the current position
is already losing for your friend, output 0.
Constraints:
1 <= T <= 20
2 <= N <= 15
1 <= s_i < 1000000000 (10^9)
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.
'''
'''
Created on May 31, 2012
@author: Leonid Braginsky
'''
"""helpers"""
import operator
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 xrange(0, n - 1) for j in xrange(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 raw_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 xrange(nt):
_n = readInt()
piles = readIntList()
answer, _fixedPiles = solve(piles)
print answer
if __name__ == "__main__":
main()
C rep HackerRank 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;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
