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