How to solve a task with C#

Question

Each person has a favorite number. Jacob’s favorite number is X and Jayden’s favorite number is Y. A non-empty array A consisting of N integers is given. Jacob and Jayden are interested in occurrences of their favorite numbers X and Y in array A. They are looking for the longest leading fragment (prefix) of array A in which there are an equal number of occurrences of X and Y. More formally, they wish to find the largest P such that ( 0 <= P <= N ) and the number of occurrences of X equals the number of occurrences of Y in the subsequence A[0], A1, …, A[P].

For example, consider X = 7, Y = 42 and the following array A:

[ A0 = 6 ]

[ A1 = 42 ]

[ A2 = 11 ]

[ A3 = 7 ]

[ A4 = 1 ]

[ A5 = 42 ]

There are three prefixes of array A containing the same number of occurrences of X and Y.

P = 0: A[0..0] = [6] contains neither 7 nor 42;

P = 3: A[O..3] = [6, 42, 11, 7] contains one 7 and one 42;

P = 4: A[O..4] = [6, 42, 11, 7, 1] also contains one 7 and one 42.

The largest value of P we are looking for is 4, because the only longer corresponding prefix A[0…5] contains one 7 and two 42s.

Jacob and Jayden have implemented a function:

class Solution { public int solution(int X, int Y, int[] A); }

which given integers X, Y and a non-empty array A consisting of N integers. returns the maximum value of P for which A[0…P] contains the same number of occurrences of X and Y, or -1 if no such value exists.

For example, given integers X, Y and array A as defined above, the function should return 4, as explained above.

For another example, given

X = 6 , Y = 13

A[0] = 13

A1 = 13

A2 = 1

A3 = 6

The function should return -1, because there is no prefix containing the same number of occurrences of 6 and 13.

Given:

X = 100, Y = 63

A0 = 100

A1 = 63

A2 = 1

A3 = 6

A4 = 2

A5 = 13

The function should return 5, because the full array contains exactly one occurrence of 100 and 63

The attached code is still incorrect for some inputs. Despite the error(s), the code may produce a correct answer for the example test cases. The goal of the exercise is to find and fix the bugs in the implementation. You can modify at most two lines.

public class Solution

{

public int Solution(int X, int Y, int[] A)

{

    int N = A.Length;

    int result = -1;

    int nX = 0;

    int nY = 0;

    for (int i = 0; i < N; i++)

    {

        if (A[i] == X)

            nX += 1;

        else if (A[i] == Y)

            nY += 1;

        if (nX == nY)

            result = i;

    }

    return result;

    }

}

Assume that:

-N is an integer within the range [1…100,000].

-X and Y are integers within the range [1…1,000,000,000].

-Each element of array A is an integer within the range [1…1,000,000,000].

In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment

I have tried this public int Solution(int X, int Y, int[] A)

{

int N = A.Length;

int result = -1;

int nX = 0;

int nY = 0;

for (int i = 0; i < N; i++)

{

    if (A[i] == X)

        nX++;

    if (A[i] == Y)

        nY++;

    if (nX == nY && nX != 0 && nY != 0)

        result = i;

}

return result;

}

This answer gave 50% correctness instead of 100%

Answer 1

Hi @Dennis Kiptoo , Welcome to Microsoft Q&A,

Here's the correct solution with the necessary modifications:

public class Solution {
    public int Solution(int X, int Y, int[] A) {
        int N = A.Length;
        int result = -1;
        int nX = 0;
        int nY = 0;

        for (int i = 0; i < N; i++) {
            if (A[i] == X)
                nX++;
            if (A[i] == Y)
                nY++;

            // Check for equal number of occurrences of X and Y
            if (nX == nY) {
                result = i;
            }
        }

        return result;
    }
}

1. Example 1:

int X = 7, Y = 42;
int[] A = {6, 42, 11, 7, 1, 42};
// Expected result: 4

1. Example 2:

int X = 6, Y = 13;
int[] A = {13, 13, 1, 6};
// Expected result: -1

1. Example 3:

int X = 100, Y = 63;
int[] A = {100, 63, 1, 6, 2, 13};
// Expected result: 5

Best Regards,

Jiale

---

If the answer is the right solution, please click "Accept Answer" and kindly upvote it. If you have extra questions about this answer, please click "Comment". 

Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.

Answer 2

Your correction assumed the input array was in ascending order, but the sample data wasn’t, the the result was the last match, not the highest.