# Groupon - Jacob and Peter

• Jacob and Peter have their favorite number `X` and `Y`, respectively. We are given an array with positive interger number and we need to find the longest prefix index which contain equal number of `X` and `Y`. We return -1 if there is no prefix with equal number of X and Y.

Suppose we have an array `A = [7,42,5,6,42,8,7,5,3,6,7]`
X = 7
Y =42
Output should be `9` as prefix will be index from 0 to 9 with equal number of X and Y.

• @StefanPochmann do you have any `O(n)` solution in mind?

• Isn't that trivial?

• @StefanPochmann not really, no. At least not for me.

• No one asked me, but:

``````int longestFavPrefix(const vector<int> &arr, int x, int y) {
int globalmax = 0, localmax = 0, cntX = 0, cntY = 0;

for(auto &&num: arr) {
localmax++;
if(num == x) cntX++;
if(num == y) cntY++;

if(cntX == cntY)
globalmax = max(localmax, globalmax);
}

return globalmax-1;
}
``````

• @babhishek21 Tried your solution, fails some test cases.

• @agave Perhaps provide me one such case.

• @babhishek21 First output is your algorithm, second output is O(n^2) brute force algorithm.

``````[0, 0, 1, 0, 0, 1, 1, 0, 0, 0]
(0, 6)
[1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0]
(10, 10)
[0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1]
(24, 24)
[0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0]
(32, 36)
[0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0]
(0, 26)
[1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1]
(2, 58)
[0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0]
(36, 36)
[1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1]
(64, 78)
[1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1]
(90, 90)
[1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1]
(30, 46)
``````

• @agave Mine is pretty much like @babhishek21's. Maybe we misunderstand the problem? How do you get `6` for input `[0, 0, 1, 0, 0, 1, 1, 0, 0, 0]`? Are `X` and `Y` zero and one? Every prefix except the empty prefix has more zeros than ones.

• @StefanPochmann Oh, OK. Sorry! My misunderstanding. I thought it was the longest SUBSTRING, not PREFIX. Yes, you're right, the problem is trivial if it's the prefix. I was trying to solve it for substring instead. How would you do it in O(n) in this case?

• This post is deleted!

• Hello, I just see this “longest substring containing same amount of X and Y question”, and I am interested. I’m thinking of something like this:

When we iterate over the array, we record and update the difference between the amount of X and Y until index i, look up the table(hashtable), and save info into the hashMap<#X-#Y,i>. It’s bit hard for me to explain it clearly, so I’ll raise an example.

Say we have an arr[7,42,42,5,7,42,7,7,42,42], X=7,Y=42.
Denote “diff” --difference between the amount of X and Y until index i, from the very start of the array.
Denote hashMap --key is the difference between amount of X and Y until index i, value is the index i.
Denote maxLen –the result we desire

Let’s say i=9, i.e we’ve iterate to the end of the array. Before entering the 9th loop, we have diff=0, hashMap={1:0,0:1,-1:2}; since arr[9] is 42, we update diff=-1, and we loop up -1 in hashtable, it exists and let’s denote the loop-up result j, then we update maxLen using i-j+1; since diff has already existed in the table as a key, we won’t update the index(we’re looking for the longest substring), if it’s not existed we just put (diff,i) into hashtable.

I think the reason we can do this is, suppose diff is valued x at index j, and later diff is updated to be x again at index i, j<i, then arr[j+1,i] including i, turns out to be a valid substring: saying we have 1X and 2Y at index j, and later we have 4X and 5Y at index i, then we know that 3X and 3Y exists between index j+1 and index i in arr.

• ``````var lIndex = -1;
var aCount = 0;var aFinalIndex = -1;
var bCount = 0;var bFinalIndex = -1;
var result = -1;
var aTurn = false;
for(var num of array)
{
lIndex++;
if(num == a){aCount++; }
if(num == b){bCount++; }

if(aCount == bCount)// && aCount != 0 && bCount != 0)
{
result = lIndex; aFinalIndex = bFinalIndex = lIndex;
}
else if(aCount > bCount && aTurn == true){ aFinalIndex = lIndex; aTurn = false;}
else if(bCount > aCount && aTurn == false){ bFinalIndex = lIndex; aTurn = true;}
}

if(aFinalIndex != bFinalIndex)
{
result = Math.max(aFinalIndex, bFinalIndex) - 1;
}

return result;
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.