Setter : harijey
Tester : rohinth_076
Editorialist : sooriya123
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
Alice and bob are going to play a game. There are N cities.Alice from left and bob from right start capturing the cities . If they want to capture a city , they need to stay a[i]
seconds in that city. If alice capture a city first then bob can’t capture that city and vice versa . Who capture the more number of city is the winner of the game.
You want to find who will be the winner of the game. Print ALICE
or BOB who wins the game .If both capture same amount of city then print TIE .
Input:
6
1 2 3 4 4 6
Output:
ALICE
EXPLANATION:
- After 10 Seconds Alice capture first 4 cities and bob capture last 2 cities only . So alice is the winner
General Approach:
Count the city of Alice from the left if it is greater than Bob(ie. counted city from the right). If Alice has greater number she would need that number to no.of seconds to capture the city,at the mean time bob will capture cities on his sides or vice versa.when all the cities are capture display the winner (person who has most cities) or display “TIE” (if score are equal)
TIME COMPLEXITY:
O(n) for each test case.
SOLUTION:
import java.io.*;
import java.util.*;
class Solution{
static Scanner fs = new Scanner(System.in);
static PrintWriter out = new PrintWriter(System.out);
public static void main(String[] args) {
int n = fs.nextInt();
int[] a = new int[n];
for(int i=0;i<n;i++)
a[i] = fs.nextInt();
int i = 0,j = n-1,as = 0,bs = 0;
while(i<j){
if(as<=bs){
as += a[i];
i++;
}
else{
bs += a[j];
j--;
}
}
int k = n-j;
if(i > k)
out.println("alice");
else if(i < k)
out.println("bob");
else
out.println("tie");
out.flush();
}
}