Array elements elimination

[Taz]

Hi everyone. I have an array with n elements and a number k. I need to eliminate elements from the array from k to k positions until I have one element left in the array. The elements start from position 1. Can anyone give me a hint for the circular array algorithm?
Example:
n=5 k=2
1 2 3 4 5
1 3 4 5
1 3 5
3 5
3
Thanks in advance,
Taz

[Duthomhas]

How did you do that example above?

Let's see.

Given 1 2 3 4 5, n=5, k=2, i=0 ('i' is your current index into the array).


Increment 'i' by 'k' to know which element to delete.

The second element of the array is 1 [2] 3 4 5, so well delete it.
Since you deleted the element a 'i', you need to decrement it by one. i = i - 1;

Now you have 1 3 4 5, n=4, k=2, i=1.


Increment 'i' by 'k' to know which element to delete.

That is 1 3 [4] 5. Deleting it, and adjusting 'i' as we did before,

leaves 1 3 5, n=3, k=2, i=2.


Increment 'i' by 'k' to know which element to delete. But wait, now i=4 > n=3, so you need to subtract the size of the array from 'i': i = i - n;

Now you have an element to delete: [1] 3 5. Delete it and adjust 'i' and 'n' as before,

giving 3 5, n=2, k=2, i=0.


Increment 'i' by 'k' to know which element to delete.

That gives 3 [5]. Delete it as always.


At this point, there is only one element left: 3, n=1, k=2, i=whatever.

Hope this helps.

[edit] Oh yeah, don't forget that in C and C++, all arrays begin at index 0. You'll have to adjust for that.

[kevinkjt2000]

Not quite sure if this is what you want but....(I am calling the array x and k is of course k and I assume they are of type int and already have been initialized)

for(int i=n-1, j=0; i>0; i--)
{
	j=j+k-1;
	if (j>i) j=j-i-1;
	for (int l=j; l < i; l++)
		x[l] = x[l+1];
	x[i] = 0;
}

[pyschoder]

i think what he/she is trying to say is that the value of k varies. am i right??

[Duthomhas]

No, k does not vary. This is a common homework assignment. Read my post.

[wasabi]

There's also the question of what to do for k>2, since Duoas' pseudo-code simply goes deleting the k'th (starting from 1) term in the sequence. Therefore, for k=3, it will never be able to clear the array until it only has 1 element.

1 2 [3] 4 5
1 2 [4] 5
1 2 [5]
1 2 []

There'd have to be a solution where it steps backwards once the last k'th term is cleared.

[kevinkjt2000]

Wasabi does my solution not work with k=3?

[Taz]

Duoas thanks for the advice, but even so, it's hard to create the "while" structure which includes that. And you're right, k is constant.
kevinkjt2000 your example is a bit ambiguous with all those iterators...
wasabi, when you reach the end of the array, you continue with the beginning of it. The array continues in circle untill it has one element left.

[kempofighter]

So far I am finding this thread to be nonsensical.

Given 1 2 3 4 5, n=5, k=2, i=0 ('i' is your current index into the array).
Increment 'i' by 'k' to know which element to delete.
The second element of the array is 1 [2] 3 4 5, so well delete it.
Since you deleted the element a 'i', you need to decrement it by one. i = i - 1;

The original problem description doesn't have enough detail for me to understand the algorithm. All of the suggested outputs look strange to me and aren't consistent with the problem description as I read it. It is as if you are treating i as a 1 based index as far as determining which element to delete yet you are starting from 0 before adding k in the first place. Conceptually I am unclear on what such an algorithm would be useful for.

In the second to last operation you have 1 3 5; k = 2 n = 3 so I am not sure why you want to remove 1. Isn't the five betwen k and K+K? I was with you up until that point and then you lost me. In the other examples you are deleting what is between k and k + k essentially where k is a 1 based index.

[syneris]

Duoas gave the answer, just didn't write the code.

while n > 1 //since you only want 1 element left
{
i+k
while index location > array size
{
i - n //loop around to new index
}
//remove element from array here
n - 1 // new array size
i - 1 // fix index location
}

Same thing. Like also mentioned, remember index 0 is 'position 1' in c type arrays. Unless I'm overlooking something, this should work with any positive int value less than half the type's max for n and k.

[Taz]

I got it how it's done. Thanks for the help, guys!

[syneris]

Surprised I didn't get corrected on this. Using mod to loop the array instead of the while you can forget about only being able to work with half the type max.