CODEWITHSUNDEEP
c++algorithmlinked-list
iRobot
iRobot

Reputation: 79

Coming up with simple formula for linked list

I've been at this for days honestly. I've already implememnted the hard part of this function, but now theres just one small thing. The method I want to write is to remove every Nth block of blockSize of a linked list. So if I have a linked list of size 7 {1,2,3,4,5,6,7}, N=2, blockSize=2, I want to remove every Nth(2nd) block of size blockSize(2), so remove 3,4,7. Now in order for my for loops to work, I need to write an expression for an int value I created called numBlocksRemoved. It calculates the total number of blocks to be removed. In this case, it would be 2. Here's what I have:

numBlockRemoved=(size/blockSize)/N;

However, this only works sometimes, when the numbers are looking good. If I have size=8,N=2, blockSize=2, then I get numBlockRemoved=2, which is correct. However, for the above example, I get in int value of 1, which is incorrect. I want 2. I've thought about this for soooo long its ridiculous. I just cant come up with a formula that works for numBlockRemoved. Any ideas?

Upvotes: 2

Views: 309

Answers (4)

Martin DeMello
Martin DeMello

Reputation: 12346

Just think about it systematically - if you take every Nth block of size blockSize, you are effectively removing "superblocks" of size (N * blockSize). So to a first approximation, you have

nBlocks = floor [size / (N * blockSize)]

Now, from your example, even if you don't get a complete block at the end, you still want to remove it. This happens if the remainder after removing the last complete block is more than (N-1) complete blocks. So the algorithm is

superblock = N * blockSize
nBlocks = floor (size / superblock)
remainder = size - (nBlocks * superblock)
if remainder > (N - 1) * blockSize {
  nBlocks += 1
}

You can collapse the +1 adjustment at the end into the formula by adding an amount that will tip the size over a complete superblock iff it is less than one block away (analogous to rounding by adding .5 and then taking the floor). Since this happens if we are even one number into the last block of the superblock, we have to add (blockSize - 1), which gives us

(size + (blockSize - 1)) / (blockSize * N)

Which is aaz's formula above. So you can go ahead and mark his answer as accepted; I just wanted to explain how he arrived at that formula.

Upvotes: 0

Eelvex
Eelvex

Reputation: 9143

Try

floor(ceil(size/blockSize)/N)

floor(ceil(7/2)/3) = 1
floor(ceil(7/2)/2) = 2
floor(ceil(8/2)/2) = 2

The number of blocks that you have:

blocks = ceil(size/blockSize)

ceil because you don't mind for not-full blocks.

then you skip every N, so:

floor(blocks/N)

floor because you either count a block or you don't.

Upvotes: 3

AProgrammer
AProgrammer

Reputation: 52314

Rounding should be upward when computing the number of blocks as an incomplete block is still a block (but not when computing the number of removed blocks):

numBlockRemoved=((size+blockSize-1)/blockSize)/N;

Upvotes: 2

aaz
aaz

Reputation: 5196

(size + (blockSize - 1)) / (blockSize * N)

Upvotes: 1

Related Questions