7.4 Replace and remove - Purpose of "size"

#1

Without reading the provided solution (which I’d like to delay doing as long as possible), it’s unclear to me what “size” means in the problem description.

The example given to illustrate the use of size is: an array <a,b,a,c,_> and size 4, where <d,d,d,d,c> is the result after performing the replace and remove operations.

In the example, what is the number of entries that the operations have been applied to?

Is it 3, because we replaced and removed 2 a’s and 1 b? Or is it 5, because, in the course of performing the operations, we modified the entries in 5 positions of the array?

Also, why is the last entry in the array denoted “_”? Is it to indicate that the actual value of the entry at that position is irrelevant to the explanation being given? Or does it indicate that, at some positions in the array, there may be no entry i.e. a null value?

0 Likes
#2

Hi @lgtout,

Size is denoting how many slots in this array. Those ‘_’ you can think as placeholders.

0 Likes
#3

Thanks @tsunghsienlee.
But if size is the number of slots in the array, why is the number of slots in the example given as 4, when there actually 5 slots in the array both before and after transformation (<a,b,a,c,_> transforming to <d,d,d,d,c>)?

0 Likes
#4

In the example you gave, the size of the array is 5, not 4.

0 Likes
#5

Thanks @tsunghsienlee . Good to know.
I actually got the example directly from the problem statement in the print version of EPIJ, so there might need to be a correction in the next edition.

0 Likes
#6

Hi @lgtout,

Sorry that I misunderstood what you meant before, and I think the size is actually referring to the number of entries in the array that is valid. So in this example it is 4, and you shall always assume the number of spaces in the array is always enough.

0 Likes
#7

Thanks, @tsunghsienlee.
You said size is “the number of entries in the array that is valid”. What is the criteria for “valid”-ity?

0 Likes
#8

Valid means they are not ‘_’.

0 Likes
#9

But I thought _ is just a “conceptual” placeholder, not that the array provided may actually have the literal character _ at later positions.

The character used in the example in EPIJ is actually ␣ not _. (I didn’t know how to represent ␣ when I first posted the question.)

Is the following a valid understanding of ‘size’?

The length of the problem parameter ‘array’ may be greater than the number of characters it contains. If there are k characters and array length is n, the first k positions will be occupied by the characters. The value of the problem parameter ‘size’ is k. The result should be an array of the same length n - it’s not necessary to preserve characters that are pushed to positions >= n (0-based) due to the replace and remove operations performed.

0 Likes
#10

We shall not overcomplicate this definition. Only the contents within size is valid, others after that does not matter. I was just using ‘_’ to represent the symbol in the book. For example, size is 4, then the first 4 entries in the array will be things you shall pay attention for, and everything after that in the array does not matter.

0 Likes
#11

Thanks for your help. I was able to solve the problem.

0 Likes