HackerRank Nikita and the Game Problem Solution Yashwant Parihar, July 6, 2023August 1, 2024 In this post, we will solve HackerRank Nikita and the Game Problem Solution. Nikita just came up with a new array game. The rules are as follows: Initially, Nikita has an array of integers. In each move, Nikita must partition the array into 2 non-empty contiguous parts suchthat the sum of the elements in the left partition is equal to the sum of the elements inthe right partition. If Nikita can make such a move, she gets 1 point: otherwise, the gameends.After each successful move, Nikita discards either the left partition or the right partition and continues playing by using the remaining partition as array arr.Nikita loves this game and wants your help getting the best score possible. Given arr, can you find and print the maximum number of points she can score?For example, Nikita starts with the array arr = [1, 2, 3, 6]. She first splits it intoa1 = [1, 2, 3] and a2 = [6], then discards a2. arr = al → al = [1, 2], a2 = [3].Discard a2 leaving arr = [1,2]. This cannot be further split, so Nikita scored 2. Function Description Complete the arraySplitting function in the editor below. It should return an integer that reperesents the number of times Nikita can split the array. arraySplitting has the following parameter(s): arr: an array of integers Input FormatThe first line contains an integer t, the number of test cases.Each of the next t pairs of lines is as follows: The first line contains an integer n. the size of array arr. The next line contains n space-separated integers arr[i]. Output Format For each test case, print Nikita’s maximum possible score on a new line. Sample Input 3 3 3 3 3 4 2 2 2 2 7 4 1 0 1 1 0 1 Sample Output 0 2 3 HackerRank Nikita and the Game Problem Solution Nikita and the Game C Solution #include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> long long sum[16384]; int getPoint(int low, int high, long long target) { int point, tmp, start, end, mid; start = low; end = high; point = 0; while (start <= end) { mid = (start+end)/2; if (sum[high]-sum[mid] < target) { end = mid - 1; } else if (sum[high]-sum[mid] > target) { start = mid + 1; } else { if (target%2 == 0) { point = getPoint(low, mid, target/2); tmp = getPoint(mid+1, high, target/2); if (tmp > point) { point = tmp; } } point += 1; break; } } return point; } int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ int t, n, i, j, num; scanf("%d", &t); for (i=0; i<t; i++) { scanf("%d", &n); scanf("%d", &num); sum[0] = num; for (j=1; j<n; j++) { scanf("%d", &num); sum[j] = sum[j-1] + num; } if (sum[n-1] == 0) { printf("%d\n", n-1); } else { if (sum[n-1]%2 == 0) { printf("%d\n", getPoint(0, n-1, sum[n-1]/2)); } else { printf("0\n"); } } } return 0; } Nikita and the Game C++ Solution #include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include<bits/stdc++.h> using namespace std; typedef long long int ll; ll n,arr[999999], d=0; ll suml=0,sumr=0; ll desti(ll st,ll en) {//cout<<"st: "<<st <<"en :"<<en<<endl; //ll i=st,j=en; if(st>n || st<0 || en>n || en<0) return 0; else{ stack<ll> s,s1; suml=0,sumr=0; for(ll i=st;i<en;i++) { s.push(arr[i]); suml+=s.top(); }//return suml; if(suml==0) return s.size()-1; ll flag=0; while(suml!=sumr && s.empty()==0) {//cout<<"suml: "<<suml<<" sumr: "<<sumr<<endl; if(suml>sumr) {s1.push(s.top()); s.pop(); sumr+=s1.top(); suml-=s1.top(); } else if(suml<sumr || s.empty()==1) {flag=1; //cout<<"break"<<endl; break;} } if(flag!=1 && suml==sumr) {//cout<<"return"<<s.size()<<endl; return s.size()+st; } } return 0; } ll part(ll st,ll en) { ll d=desti(st,en); if(d==0) return 0; /*if(d==-1) return -1; */ return max(1+part(st,d),1+part(d,en)); } int main() { ll t; cin>>t; while(t--) { cin>>n; for(ll i=0;i<n;i++) {cin>>arr[i];} /* ll a=part(0,n); if(a==1 && suml==0) cout<<0; else cout<<a<<endl; */ cout<<part(0,n)<<endl; //cout<< desti(0,n)<<endl; } /* Enter your code here. Read input from STDIN. Prll output to STDOUT */ return 0; } Nikita and the Game C Sharp Solution using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { static void Main(String[] args) { int t = int.Parse(Console.ReadLine()); for(int i = 0; i<t; i++){ TestCase(); } } static void TestCase(){ int n = int.Parse(Console.ReadLine()); int[] a = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse); long sum = 0; foreach(int i in a){ sum+= i; } hash = new Dictionary<string, int>(); Console.WriteLine(Score(a, 0, a.Length-1, sum)); } static Dictionary<string, int> hash; static int Score(int[] a, int left, int right, long sum){ string key = left + "," + right; if(hash.ContainsKey(key)){ return hash[key]; } if (right == left ){ // can't partition single element return 0; } if (sum % 2 == 1) { // partition failed - sum is odd return 0; } long leftSum = a[left]; int p = left; while(leftSum < sum/2){ p++; leftSum+=a[p]; } if (leftSum != sum/2){ // partition failed to find equal halves return 0; } int result = 1 + Math.Max(Score(a, left, p, sum/2), Score(a, p+1, right, sum/2)); hash[key] = result; return result; } } Nikita and the Game Java Solution import java.io.*; import java.util.*; public class Solution { public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ Scanner scan = new Scanner (System.in); int t = scan.nextInt(); for(int a_0=0;a_0<t;a_0++){ int n= scan.nextInt(); int [] arr = new int [n]; long[]sum = new long [n]; for(int a_i=0;a_i<n;a_i++){ arr[a_i]= scan.nextInt(); if (a_i>0) sum[a_i] = (long)arr[a_i]+sum[a_i-1]; else sum[0]= (long)arr[0]; } int score = index(sum,0); System.out.println(score); } } static int index(long []arr ,int score) { int l = arr.length-1; if (arr[l]==0){ score = l; return score; } if (l == 0) return score; else if (arr[l]%2 != 0) return score; else{ int pos = Arrays.binarySearch(arr,arr[l]/2); //for (int check : arr) //System.out.print(check + " "); //System.out.println("pos "+ pos +" arr[l] "+arr[l] +" arr[l]/2 " + arr[l]/2); if (pos < 0){ //System.out.println("Score!! " + score); return score; } long [] left = new long [pos+1]; long [] right = new long [l-pos]; System.arraycopy(arr,0,left,0,pos+1); System.arraycopy(arr,pos+1,right,0,l-pos); for (int i = 0; i<right.length; i++) right[i]-=left[pos]; int scoreleft = index (left,score+1); int scoreright = index(right,score+1); score = Math.max(scoreleft,scoreright); //System.out.println("Problem"); return score; } } } Nikita and the Game JavaScript Solution process.stdin.resume(); process.stdin.setEncoding("ascii"); var input = ""; process.stdin.on("data", function (chunk) { input += chunk; }); process.stdin.on("end", function () { // now we can read/parse input var arr = input.split("\n"); cnt= parseInt(arr[0]); // count of samples // console.log(cnt); for(var e=0 ; e < arr.length-2; e=e+2) { var sample = arr[e+2].split(" "); // console.log(sample); var points= tryToSplit(sample); console.log(points); } }); function tryToSplit (arr) { var sum= 0; var tmp= 0; var i=0; for(i=0 ; i<arr.length;i++) { sum += parseInt(arr[i]); } if (sum %2 || arr.length ==1 ) return 0; if (sum==0) return arr.length-1; for(i=0;i<arr.length;i++) { tmp+=parseInt(arr[i]); if (tmp == sum / 2) { var arr1= arr.slice(0,i +1); var arr2= arr.slice(i + 1 , arr.length); var pt1= tryToSplit(arr1); var pt2= tryToSplit(arr2); if (pt1 > pt2 ) { return 1 +pt1; } else { return 1 + pt2; } } if (tmp> sum/2) return 0; } } Nikita and the Game Python Solution def findSplit(A): Lsum = 0 Lind = -1 Rsum = 0 Rind = len(A) splits = 0 while Rind - Lind > 1: #print("intermediate",Lind,Rind,Lsum,Rsum) if(Lsum <= Rsum): Lind += 1 Lsum += A[Lind] else: Rind -= 1 Rsum += A[Rind] if(Rsum == Lsum): splits = 1 Lsplits = 0 Rsplits = 0 if(Lind >= 1): #print("going left") if(Lsum != 0): Lsplits = findSplit(A[0:Lind+1]) else: return len(A)-1 if(Rind <= len(A)-2): #print("going right",A,Rind) Rsplits = findSplit(A[Rind:]) splits += max(Lsplits,Rsplits) #print(A,Lind,Rind,Rsum,Lsum,splits) return splits T = int(input()) for i in range(0,T): N = int(input()) A = [int(x) for x in input().split()] print(findSplit(A)) c C# C++ HackerRank Solutions java javascript python CcppCSharpHackerrank Solutionsjavajavascriptpython