Stone 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<iostream>
#include<algorithm>
#include<cstdio>
#include<complex>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<string>
#include<cstdlib>
#include<memory.h>
#include<ctime>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ld,ld> pdd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef pair<ll,ll> pl;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define SORT(v) sort((v).begin(),(v).end())
#define UN(v) SORT(v),(v).erase(unique((v).begin(),(v).end()),(v).end())
#define CL(a,b) memset(a,b,sizeof a)
#define pb push_back
const int mod = 1000000007;
int n;
int a[111],b[111];
void add(ll &x,ll v){
x+=v;
x%=mod;
}
ll r[111][2];
ll qp(ll c,ll st){
ll r = 1;
while(st){
if(st&1)r*=c,r%=mod;
c*=c,c%=mod;
st>>=1;
}
return r;
}
int solve(){
ll res = 0;
for(int pos=30;pos>=0;pos--){
vi v;
REP(j,n)if(a[j]&(1<<pos))v.pb(j);
CL(r,0);
r[0][0] = 1;
REP(j,n)REP(t,2)if(r[j][t]){
ll val = r[j][t];
if(a[j]&(1<<pos)){
add(r[j+1][t], val * (1<<pos));
add(r[j+1][t^1], val * (a[j] - (1<<pos) + 1));
}else{
add(r[j+1][t], val * (a[j]+1));
}
}
//cout<<"start "<<pos<<" -> "<<res<<' '<<r[n][0]<<endl;
res += r[n][0] * qp((1<<pos),mod-2);
res %= mod;
//cout<<"add "<<res<<endl;
if(v.size()%2==0){
ll t = 1;
REP(j,n)if(a[j]&(1<<pos)) t=(t*(a[j]-(1<<pos)+1))%mod;//,cout<<"mult1 "<<a[j]-(1<<pos)+1<<endl;
else t=(t*(a[j]+1))%mod;//,cout<<"mult2 "<<a[j]+1<<endl;
//cout<<t<<endl;
t *= qp((1<<pos),mod-2);
t%=mod;
// cout<<pos<<' '<<t<<endl;
res -= t;
res %= mod;
if(res<0) res += mod;
}else return res;
REP(j,n)if(a[j]&(1<<pos))a[j]^=(1<<pos);
}
res++;
//cout<<"!"<<res<<endl;
return res;
}
int main(){
#ifdef LocalHost
freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
#endif
cin>>n;
REP(i,n) cin>>a[i],b[i]=a[i];
int res = solve();
REP(i,n) a[i]=b[i]-1;
res -= solve();
if(res<0) res += mod;
cout<<res<<endl;
//stupid();
//cout<<rr<<endl;
#ifdef LocalHost
// printf("TIME: %.3lf\n",ld(clock())/CLOCKS_PER_SEC);
#endif
return 0;
}
Java rep HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class Solution {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
static void solve()
{
int n = ni();
int[] a = na(n);
int mod = 1000000007;
long ret = 0;
int w = 0;
while(true){
int max = 0;
int maxi = -1;
for(int i = 0;i < n;i++){
if(a[i] > max){
max = a[i];
maxi = i;
}
}
if(max == 0){
if(w == 0)ret++;
break;
}
int h = Integer.highestOneBit(max); // to 0
if(w == 0 || w == h){
long[][][] dp = new long[n+1][2][2];
dp[0][w==0?0:1][0] = 1;
for(int i = 0;i < n;i++){
if(i == maxi){
for(int j = 0;j < 2;j++){
for(int k = 0;k < 2;k++){
dp[i+1][j][k] = dp[i][j][k];
}
}
}else{
if(a[i] < h){
dp[i+1][0][0] = dp[i][0][0] * (a[i]) % mod;
dp[i+1][1][0] = dp[i][1][0] * (a[i]) % mod;
dp[i+1][0][1] = (dp[i][0][1] * (a[i]+1) + dp[i][0][0]) % mod;
dp[i+1][1][1] = (dp[i][1][1] * (a[i]+1) + dp[i][1][0]) % mod;
}else{
dp[i+1][0][0] = (dp[i][0][0] * h + dp[i][1][0] * (a[i]-h)) % mod;
dp[i+1][1][0] = (dp[i][1][0] * h + dp[i][0][0] * (a[i]-h)) % mod;
dp[i+1][0][1] = (dp[i][0][1] * h + dp[i][1][1] * (a[i]-h+1) + dp[i][1][0]) % mod;
dp[i+1][1][1] = (dp[i][1][1] * h + dp[i][0][1] * (a[i]-h+1) + dp[i][0][0]) % mod;
}
}
}
ret += dp[n][0][1];
}
a[maxi] -= h;
w ^= h;
}
out.println(ret%mod);
}
public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}
private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;
private static int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
Python 3 rep HackerRank Solution
import operator as op
import functools as ft
from sys import stderr
MOD = 1000000007
def readcase():
npiles = int(input())
piles = [int(fld) for fld in input().split()]
assert npiles == len(piles)
return piles
def numsolns(piles):
return (numunrestrictedsolns(piles) -
numunrestrictedsolns([pile-1 for pile in piles if pile > 1])) % MOD
def numunrestrictedsolns(piles, MOD=MOD):
if len(piles) == 0:
return 1
xorall = ft.reduce(op.xor, piles)
leftmost = ft.reduce(op.or_, piles).bit_length() - 1
rightmost = max(0, xorall.bit_length() - 1)
ans = 0
for first1 in range(rightmost, leftmost+1):
premult = 1
matchbit = 1 << first1
# print('first1 =', first1, file=stderr)
for i, bigalt in enumerate(piles):
if bigalt & matchbit != 0:
even = 1
odd = 0
for pile in piles[i+1:]:
neweven = (1 + (pile & ~-matchbit)) * even
newodd = (1 + (pile & ~-matchbit)) * odd
if pile & matchbit != 0:
neweven += matchbit * odd
newodd += matchbit * even
even, odd = neweven % MOD, newodd % MOD
# print(i, even, odd, ans, file=stderr)
ans += (even if xorall & matchbit != 0 else odd) * premult % MOD
# print(ans, premult, file=stderr)
premult = (premult * ((bigalt & ~-matchbit) + 1)) % MOD
if xorall == 0:
ans += 1
return ans % MOD
print(numsolns(readcase()))
Python 2 rep HackerRank Solution
#!/usr/bin/env python
from itertools import izip, chain
M=10**9+7
def gao(A, j):
if j==-1: return 1
s = sum((A[i]>>j)&1 for i in xrange(len(A)))
zprod = reduce(lambda x,y:x*y%M, (m%2**j+1 for m in A if not (m>>j)&1), 1)
factors=[m%2**j+1 for m in A if (m>>j)&1]
poly=[1]
for f in factors: # multiplying a bunch of linear factors together
poly = [(a*f%M+b)%M for a,b in izip(chain([0],poly),chain(poly,[0]))]
ans = 0 if (s&1) else gao(A,j-1)
for i in xrange(2-(s&1),s+1,2):
ans = (ans + zprod*poly[s-i]%M*pow(2,(i-1)*j,M)%M)%M
return ans
n=input()
p=map(int, raw_input().strip().split())
print (gao(p,29) - gao([x-1 for x in p],29))%M
C rep HackerRank Solution
#include <stdio.h>
#define P 1000000007LL
long long a[200][2][2][2],i,j,k,l,m[100],n,v,b[200],x,t, im[100];
long long poww(long long xx, long long nn)
{
long long zz,vv;
vv = 1;
zz = xx;
while(nn)
{
if(nn&1) vv = (vv*zz)%P;
zz = (zz*zz)%P;
nn/=2;
}
return vv;
}
int main()
{
scanf("%lld",&n);
for(i=0;i<n;i++) scanf("%lld",b+i);
m[0] = 1;
im[0] = 1;
for(i=1;i<=60;i++)
{
m[i] = 2*m[i-1];
im[i] = poww(m[i], P-2);
// printf("%lld %lld %lld\n", m[i],im[i], (m[i]*im[i])%P);
}
//return 0;
x = 0;
for(i = 0; i<n ;i++) x^=b[i];
//printf("%lld = x\n", x);
k = 40;
v = 0;
if(x==0) v++;
while(k>=0)
{
//printf("---- k = %lld ---%lld---\n",k,v);
a[0][0][0][0] = 0;
a[0][0][0][1] = 0;
if(m[k]&b[0])
a[0][0][0][1] = ((m[k]-1)&b[0]);
else
a[0][0][0][0] = ((m[k]-1)&b[0]);
a[0][0][1][0] = 0;
a[0][0][1][1] = 0;
if(b[0]&m[k])
a[0][0][1][0] = m[k];
a[0][1][0][0] = 0;
a[0][1][0][1] = 0;
if(b[0]&m[k])
a[0][1][0][1] = 1;
else
a[0][1][0][0] = 1;
a[0][1][1][0] = 0;
a[0][1][1][1] = 0;
i = 0;
/*
for(j=0;j<2;j++)
for(l=0;l<2;l++)
for(t=0;t<2;t++)
printf("i=%lld %lld %lld %lld -> %lld\n",i,j,l,t,a[i][j][l][t]);
*/
for(i=1; i<n; i++)
{
//printf("%lld %lld -> %lld\n", b[i],m[k],b[i]&m[k]);
//ma k-ty bit
if(b[i]&m[k])
{
//printf("s najvyssim bitom\n");
a[i][0][0][0] = (a[i-1][0][0][1]*((m[k]-1) & b[i]))%P;
a[i][0][0][1] = (a[i-1][0][0][0]*((m[k]-1) & b[i]))%P;
//nemazu najvyssi bit
a[i][0][1][0] = (a[i-1][0][1][1]*((m[k]-1) & b[i]))%P;
a[i][0][1][1] = (a[i-1][0][1][0]*((m[k]-1) & b[i]))%P;
//printf("1) %lld\n", (a[i-1][0][1][0]*((m[k]-1) & b[i]))%P);
//mazu najvyssi bit
a[i][0][1][0] = (a[i][0][1][0] + a[i-1][0][1][0]*m[k])%P;
a[i][0][1][1] = (a[i][0][1][1] + a[i-1][0][1][1]*m[k])%P;
a[i][0][1][0] = (a[i][0][1][0] + a[i-1][0][0][0]*m[k])%P;
a[i][0][1][1] = (a[i][0][1][1] + a[i-1][0][0][1]*m[k])%P;
// a[i][0][1][0] = (a[i][0][1][0] + a[i-1][0][0][0])%P;
// a[i][0][1][1] = (a[i][0][1][1] + a[i-1][0][0][1])%P;
a[i][1][0][0] = (a[i-1][1][0][1] * (((m[k]-1)&b[i])+1))%P;
a[i][1][0][1] = (a[i-1][1][0][0] * (((m[k]-1)&b[i])+1))%P;
a[i][1][0][0] = (a[i][1][0][0] + a[i-1][0][0][1])%P;
a[i][1][0][1] = (a[i][1][0][1] + a[i-1][0][0][0])%P;
a[i][1][1][0] = (a[i-1][1][1][0]*m[k])%P;
a[i][1][1][1] = (a[i-1][1][1][1]*m[k])%P;
//printf("-1. %lld\n",(a[i-1][1][1][0]*m[k])%P);
a[i][1][1][0] = (a[i][1][1][0] + a[i-1][1][1][1]*(((m[k]-1)&b[i])+1))%P;
a[i][1][1][1] = (a[i][1][1][1] + a[i-1][1][1][0]*(((m[k]-1)&b[i])+1))%P;
// printf("%lld...\n", (a[i-1][1][1][0]*(((m[k]-1)&b[i])+1))%P);
//printf("-2. %lld\n",(a[i-1][1][1][1]*(((m[k]-1)&b[i])+1))%P);
//prvy co sa nemeni
a[i][1][1][0] = (a[i][1][1][0] + a[i-1][0][1][1])%P;
a[i][1][1][1] = (a[i][1][1][1] + a[i-1][0][1][0])%P;
//printf("-3. %lld\n",a[i-1][0][1][1]);
//prvy co si maze najvyssi bit
a[i][1][1][0] = (a[i][1][1][0] + a[i-1][1][0][0]*m[k])%P;
a[i][1][1][1] = (a[i][1][1][1] + a[i-1][1][0][1]*m[k])%P;
// a[i][1][1][0] = (a[i][1][1][0] + a[i-1][1][0][0])%P;
// a[i][1][1][1] = (a[i][1][1][1] + a[i-1][1][0][1])%P;
// printf("%lld,,\n",(a[i-1][1][1][1]*m[k])%P);
//printf("-4. %lld\n",a[i-1][1][0][0]);
}
else
{
//printf("bez najvyssieho bitu\n");
a[i][0][0][0] = (a[i-1][0][0][0]*((m[k]-1) & b[i]))%P;
a[i][0][0][1] = (a[i-1][0][0][1]*((m[k]-1) & b[i]))%P;
//nemazu najvyssi bit
a[i][0][1][0] = (a[i-1][0][1][0]*((m[k]-1) & b[i]))%P;
a[i][0][1][1] = (a[i-1][0][1][1]*((m[k]-1) & b[i]))%P;
a[i][1][0][0] = (a[i-1][1][0][0] * (((m[k]-1)&b[i])+1))%P;
a[i][1][0][1] = (a[i-1][1][0][1] * (((m[k]-1)&b[i])+1))%P;
a[i][1][0][0] = (a[i][1][0][0] + a[i-1][0][0][0])%P;
a[i][1][0][1] = (a[i][1][0][1] + a[i-1][0][0][1])%P;
a[i][1][1][0] = (a[i-1][1][1][0]*(((m[k]-1)&b[i])+1))%P;
a[i][1][1][1] = (a[i-1][1][1][1]*(((m[k]-1)&b[i])+1))%P;
//prvy co sa nemeni
a[i][1][1][0] = (a[i][1][1][0] + a[i-1][0][1][0])%P;
a[i][1][1][1] = (a[i][1][1][1] + a[i-1][0][1][1])%P;
}
/*
for(j=0;j<2;j++)
for(l=0;l<2;l++)
for(t=0;t<2;t++)
printf("i=%lld %lld %lld %lld -> %lld\n",i,j,l,t,a[i][j][l][t]);
*/
}
v = (v + a[n-1][1][1][0]*im[k])%P;
if(x & m[k]) break;
k--;
//break;
}
printf("%lld\n",v);
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
