Table of Contents
Chocolate 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
#pragma comment(linker, "/STACK:16777216")
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<ctype.h>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<utility>
#include<algorithm>
#include<list>
using namespace std;
#define pb push_back
#define MS( a ) memset( a,0,sizeof(a))
#define MSV( a,v ) memset( a,v,sizeof(a))
#define MP make_pair
typedef long long Long;
typedef vector<long> VL;
typedef pair<long,long> pll;
#define MAX 100007
long N,K;
long A[MAX+7];
long X[MAX+7];
long Find( long *A,long n )
{
long i;
for( i=1;i<=n;i++ ){
if( i&1 ) X[i] = X[i-1];
else X[i] = X[i-2]^(A[i-1]-A[i]);
}
long Cnt = 0;
map<long,long> Map;
Map[0] = 1;
for( i=2;i<=n;i++ ){
if( i&1 ){
long v = X[i-1]^A[i];
Map[v] += 0;
Cnt += Map[v];
Map[X[i-1]]++;
}
else{
long v = X[i];
Map[v] += 0;
Cnt += Map[v];
}
}
return Cnt;
}
int main( void )
{
long i,j,v,Icase,k = 0;
//freopen("text1.txt","r",stdin );
scanf("%ld",&N );
for( i=1;i<=N;i++ ){
scanf("%ld",&A[i] );
}
reverse( A+1,A+N+1 );
Long Ans = ((Long)N*(N-1))/2 - Find( A,N ) - Find( A+1,N-1 );
cout<<Ans<<endl;
return 0;
}
Java rep HackerRank Solution
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
new Solution().run();
}
BufferedReader br;
StringTokenizer in;
PrintWriter out;
public String nextToken() throws IOException {
while (in == null || !in.hasMoreTokens()) {
in = new StringTokenizer(br.readLine());
}
return in.nextToken();
}
public int nextInt() throws IOException {
return Integer.parseInt(nextToken());
}
public long nextLong() throws IOException {
return Long.parseLong(nextToken());
}
public void solve(int n) throws IOException {
int[] a = new int[n];
for (int i = 0; i < a.length; i++) {
a[i] = nextInt();
}
long ans = 0;
for (int st = 2; st <= 3; st++) {
HashMap<Integer, Integer> cnt = new HashMap<>();
cnt.put(0, 1);
int xor = 0;
for (int i = a.length - st; i >= 0; i -= 2) {
xor ^= a[i + 1] - a[i];
if (!cnt.containsKey(xor)) {
cnt.put(xor, 0);
}
int z = cnt.get(xor);
ans += z;
cnt.put(xor, z + 1);
if (i > 0) {
if (cnt.containsKey(xor ^ a[i - 1])) {
ans += cnt.get(xor ^ a[i - 1]);
}
}
}
}
out.println(1L * n * (n - 1) / 2 - ans);
}
public void run() {
try {
br = new BufferedReader(new InputStreamReader(System.in));
out = new PrintWriter(System.out);
solve(nextInt());
out.close();
} catch (IOException e) {
e.printStackTrace();
System.exit(1);
}
}
}
Python 3 rep HackerRank Solution
from operator import xor
from itertools import accumulate, chain
from collections import defaultdict
from bisect import bisect
from sys import stderr
def main():
npiles = int(input())
piles = [int(f) for f in input().split()]
assert len(piles) == npiles
print(countwins(piles))
def countwins(piles):
loses = 0
diff = [a-b for a, b in zip(piles[1:], piles)]
for start in (0, 1):
df = diff[start::2]
cumxor = list(chain([0], accumulate(df, xor)))
cxlocs = defaultdict(list)
for i, x in enumerate(cumxor):
cxlocs[x].append(i)
loses += sum(x*(x-1)//2 for x in map(len, cxlocs.values()))
# print(loses, df, cumxor, cxlocs, file=stderr)
for seqstart in range(1-start, len(piles)-2, 2):
inextpair = (seqstart+1)//2
locs = cxlocs[piles[seqstart] ^ cumxor[inextpair]]
firstlose = bisect(locs, inextpair)
loses += len(locs) - firstlose
return len(piles)*(len(piles)-1)//2 - loses
main()
Python 2 rep HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
n = int(raw_input())
v = map(int,raw_input().split())
s = [0,0]
for i in range(2,n+1):
s.append(s[i-2] ^ (v[i-1] - v[i-2]))
cnt = [dict(), dict()]
res = 0
for i in range(n-2,-1,-1):
cnt[i&1][s[i+2]] = 1 + cnt[i&1].get(s[i+2],0)
res += cnt[i&1].get(s[i],0) + cnt[(i^1)&1].get(v[i]^s[i+1],0)
print n*(n-1)/2 - res
C rep HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
void sort_a(int*a,int *c,int size,int*new_size);
void merge(int*a,int*left,int*right,int *c,int*c_left,int*c_right,int left_size, int right_size,int*new_size);
int get_i(int*a,int num,int size);
int med(int*a,int size);
int main(){
int n,evensize,oddsize,sort_evensize,sort_oddsize,i,j,t;
int *d,*dd,*dseven,*dsodd,*sort_even,*sort_odd,*c_even,*c_odd,**even_table,**odd_table;
long long ans=0;
scanf("%d",&n);
d=(int*)malloc(n*sizeof(int));
dd=(int*)malloc((n-1)*sizeof(int));
evensize=oddsize=(n-1)/2;
evensize+=(n-1)%2;
dseven=(int*)malloc(evensize*sizeof(int));
dsodd=(int*)malloc(oddsize*sizeof(int));
sort_even=(int*)malloc(evensize*sizeof(int));
sort_odd=(int*)malloc(oddsize*sizeof(int));
c_even=(int*)malloc(evensize*sizeof(int));
c_odd=(int*)malloc(oddsize*sizeof(int));
for(i=0;i<n;i++)
scanf("%d",d+i);
for(i=0;i<n-1;i++){
dd[i]=d[i+1]-d[i];
if(!i)
dseven[i/2]=dd[i];
else if(i==1)
dsodd[i/2]=dd[i];
else if(i%2)
dsodd[i/2]=dsodd[i/2-1]^dd[i];
else
dseven[i/2]=dseven[i/2-1]^dd[i];
}
for(i=0;i<evensize;i++){
sort_even[i]=dseven[i];
c_even[i]=1;
}
for(i=0;i<oddsize;i++){
sort_odd[i]=dsodd[i];
c_odd[i]=1;
}
sort_a(sort_even,c_even,evensize,&sort_evensize);
sort_a(sort_odd,c_odd,oddsize,&sort_oddsize);
even_table=(int**)malloc(sort_evensize*sizeof(int*));
for(i=0;i<sort_evensize;i++){
even_table[i]=(int*)malloc((c_even[i]+1)*sizeof(int));
even_table[i][0]=0;
}
odd_table=(int**)malloc(sort_oddsize*sizeof(int*));
for(i=0;i<sort_oddsize;i++){
odd_table[i]=(int*)malloc((c_odd[i]+1)*sizeof(int));
odd_table[i][0]=0;
}
for(i=0;i<evensize;i++){
j=get_i(sort_even,dseven[i],sort_evensize);
even_table[j][++even_table[j][0]]=i;
}
for(i=0;i<oddsize;i++){
j=get_i(sort_odd,dsodd[i],sort_oddsize);
odd_table[j][++odd_table[j][0]]=i;
}
for(i=0;i<n-1;i++)
if(i%2){
t=d[i]^dseven[(i-1)/2];
j=get_i(sort_even,t,sort_evensize);
if(j>=0 && j<sort_evensize && sort_even[j]==t){
t=get_i(even_table[j]+1,(i+1)/2,even_table[j][0]);
ans+=even_table[j][0]-t;
}
t=0;
if(i!=1)
t^=dsodd[(i-2)/2];
j=get_i(sort_odd,t,sort_oddsize);
if(j>=0 && j<sort_oddsize && sort_odd[j]==t){
t=get_i(odd_table[j]+1,i/2,odd_table[j][0]);
ans+=odd_table[j][0]-t;
}
}
else{
t=d[i];
if(i)
t^=dsodd[(i-1)/2];
j=get_i(sort_odd,t,sort_oddsize);
if(j>=0 && j<sort_oddsize && sort_odd[j]==t){
t=get_i(odd_table[j]+1,i/2,odd_table[j][0]);
ans+=odd_table[j][0]-t;
}
t=0;
if(i)
t^=dseven[(i-1)/2];
j=get_i(sort_even,t,sort_evensize);
if(j>=0 && j<sort_evensize && sort_even[j]==t){
t=get_i(even_table[j]+1,i/2,even_table[j][0]);
ans+=even_table[j][0]-t;
}
}
ans=((long long)n)*(n-1)/2-ans;
printf("%lld",ans);
return 0;
}
void sort_a(int*a,int *c,int size,int*new_size){
if (size < 2){
(*new_size)=size;
return;
}
int m = (size+1)/2,i;
int *left,*right,*c_left,*c_right;
left=(int*)malloc(m*sizeof(int));
right=(int*)malloc((size-m)*sizeof(int));
c_left=(int*)malloc(m*sizeof(int));
c_right=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left[i]=a[i];
c_left[i]=c[i];
}
for(i=0;i<size-m;i++){
right[i]=a[i+m];
c_right[i]=c[i+m];
}
int new_l_size=0,new_r_size=0;
sort_a(left,c_left,m,&new_l_size);
sort_a(right,c_right,size-m,&new_r_size);
merge(a,left,right,c,c_left,c_right,new_l_size,new_r_size,new_size);
free(left);
free(right);
free(c_left);
free(c_right);
return;
}
void merge(int*a,int*left,int*right,int *c,int*c_left,int*c_right,int left_size, int right_size,int*new_size){
int i = 0, j = 0,index=0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
c[index] = c_right[j];
a[index++] = right[j];
j++;
} else if (j == right_size) {
c[index] = c_left[i];
a[index++] = left[i];
i++;
} else if (left[i] <= right[j]) {
c[index] = c_left[i];
a[index++] = left[i];
i++;
} else {
c[index] = c_right[j];
a[index++] = right[j];
j++;
}
if(index>1&&a[index-2]==a[index-1]){
index--;
c[index-1]+=c[index];
}
}
(*new_size)=index;
return;
}
int get_i(int*a,int num,int size){
if(size==0)
return 0;
if(num>med(a,size))
return get_i(&a[(size+1)>>1],num,size>>1)+((size+1)>>1);
else
return get_i(a,num,(size-1)>>1);
}
int med(int*a,int size){
return a[(size-1)>>1];
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
