Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Weird Faculty

Sharing is caring!

Problem Statement
This semester you are taking a course taught by a faculty member who has a weird way of grading tests. In a test, n questions will be asked, and the correctness of the answers is already determined. For the ith question, the verdict will be v[i] (where 0 ≤ i < n). If v[i] = 1, the answer is correct but if v[i] = 0, the answer is wrong.

When a test is given, you have to answer the first k questions (indices 0 to k-1) where 0 ≤ k < n, and your friend has to answer the remaining questions (indices k to n-1) on the test. At the end, results are calculated as follows:

Your results:

int Your_result = 0;
for(int i=0;i<k;i++)
{
    if(v[i]==1)
        Your_result++;
    else Your_result--; 
}

Your friend’s results:

int YourFriend_result = 0;
for(int i=k;i<n;i++)
{
    if(v[i]==1)
        YourFriend_result++;
    else YourFriend_result--; 
}

Choose the minimum k such that Your_result > YourFriend_result.

Function Description
Complete the function exam in the editor below. The function must return an integer that denotes the minimum number of questions you must answer to have Your_result > YourFriend_result.

exam has the following parameter(s):

v[v[0],…v[n-1]]: an array of integers

Constraints
1 ≤ n ≤ 105
v[i] ∈ {0,1} (where 0 ≤ i < n)

Sample Input 0

5
1
0
0
1
0

Sample Output 0

0

Explanation 0
n = 5
v = {1, 0, 0, 1, 0}

If you answer 0 questions (k=0) then Your_result = 0 and YourFriend_result = -1 (2 correct answers & 3 wrong answers).

Solution

public class WeirdFaculty {

    public static int exam(int[] a) {
        int n = a.length;

        int[] onesUntilIndex = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            onesUntilIndex[i] = a[i - 1] == 1 ? onesUntilIndex[i - 1] + 1 : onesUntilIndex[i - 1];
        }

        int k = 0;
        for (int i = 0; i <= n; i++) {
            int your_ones = onesUntilIndex[i];
            int you_zeros = i - your_ones;
            int your_sum = your_ones - you_zeros;

            int friend_ones = onesUntilIndex[n] - your_ones;
            int friend_zeros = (n - i) - friend_ones;
            int friend_sum = friend_ones - friend_zeros;

            if (your_sum > friend_sum) {
                k = i;
                break;
            }
        }

        return k;
    }

    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt"));
        //Scanner outputScanner = new Scanner(new FileInputStream(System.getProperty("user.home") + "/" + "out.txt"));

        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(scanner.next());
            a[i] = x;
        }

        System.out.println(exam(a));
    }
}