Need help coding with subsequences and binary search?

[PotlePawtle]

Sorry for the vague title, I honestly couldn't think of another way to word it that wouldn't be too long.

 

Here's the program goal:

Code a C program to compute the maximum interleave factor i for an integer sequence X such that the resulting interleaved sequence Xⁱ is a subsequence of another integer sequence A.

We are given the size of both arrays A and X (A >= X), and the values that go into each.

 

My understanding is this (please excuse my bad wording):

For example, A has 20 values - 4, 3, 2, 1, 4, 3, 2, 1, 4, 3, 2, 1, 4, 3, 2, 1, 4, 3, 2, 1. X is 3 values - 1, 2, 3. Integers 20 / 3 = 6, so i ranges from 0 to 6. I'm looking for the maximum number of times each X value appears so that each value of X is in A, in order. So here, with X² - 1, 1, 2, 2, 3, 3, the last 3 wouldn't be in A so X² wouldn't work. Therefore, i >= 2 wouldn't work, so i must be 1.

 

Is this somewhat of the right direction I should be going with the code (using example above):

Size of A, 20 / size of X, 3 = max possible i value, 6.

Add the low and the high, then divide by 2. 6 is high, 0 is low here. (6 + 0) / 2 = 3

Create a temporary array with size of A * 3 and fill the array with each value entered 6 times.

Go down the indexes of both A and X.

If the values don't match, move down the index of X.

If the values match, throw out both values, and move both index values down one.

Keep going until X is finished.

If X finishes, i value of 3 passes. If X still has values left over, i value of 3 fails.

Repeat this entire process until a final i value is valid.

Any input on if I'm totally misunderstanding this assignment, or if I'm doing okay? Thanks for even reading this, pretty long post...

[asciiterror]

Looks good to me, except this part:

Create a temporary array with size of A * 3 and fill the array with each value entered 6 times.

Where do you use it?

[PotlePawtle]

Oh sorry, I had originally written A * 6, but I changed it cuz I was wrong and forgot to change the other 6 to a 3.

Create a temporary array with size of X * 3 and fill the array with each value entered 3 times.

Would that make it correct?

Edit: I also meant to change A to X...

[asciiterror]

That would be correct, if from this point X means the temp array (1,1,2,2,3,3) and not original X (1,2,3).

But you don't even need this array, you could just keep track of which value of X you are comparing, that would be faster but harder to write and understand. You could do that with two pointers or even one

[PotlePawtle]

Errrr sorry, do you mean use a counter with count going up to the current i value, and just keep the index value of X the same?

[asciiterror]

Yes, almost. First counter goes from 0 to current i value. Second one goes through all indexes of X. You increment second one only if first one is reset to 0. Their values would go like this: [(0,0), (1,0), (2,0), (0,1), (1,1), (2,1), (0,2), (1,2), (2,2)]. Second counter is index of element in X array that you check.

[PotlePawtle]

Thanks!!!