Delete mth element from an array

Given an array of size n, I need to a write a function which deletes every mth element in the array till only one element exists in the array 开发者_开发问答and return that value. Can somebody just give me the hints?

Sounds like you're trying to solve the Josephus Problem:

There are people standing in a circle waiting to be executed. After the first man is executed, certain number of people are skipped and one man is executed. Then again, people are skipped and a man is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last man remains, who is given freedom.

The task is to choose the place in the initial circle so that you survive (are the last one remaining).

The wiki article includes a very simple recursive solution to the problem above: let n = number of people, k = people to skip per deletion, then:

f(1, k) = 0
f(n, k) = (f(n - 1, k) + k) % n

The naive way to do it:

• Start a pointer at element m, delete it (by delete I mean put a marker there, since you don't want to have to reconstruct a new array every time you delete something)
• Increment your pointer m times. If you are pointing to a deleted element, decrease your counter by 1, so you move past m non-deleted items. Make sure to move back to position 0 if you go off the end of the array.
• Keep track of the number of items you have deleted. Stop after n-1.

In python, which actually reconstructs the list for each run instead of deleting items. Could probably be done better.

This takes into account that the first (0th) item should be the first to go.

def lms(l, m, r=0):
    """Return last man standing in the lineup l where every mth man is
    executed."""
    if len(l) == 1: return l[0]
    return lms(
        [l[x] for x in range(len(l)) if (r + x) % m], # new list without exec.
        m,                                            # frequency
        (r + len(l)) % m)                             # remainder from this round

def get_lms(n, m):
    """Just a setup function, which creates a plain range list to serve to the function. 
    Any list of any items can be used."""
    l = [x for x in range(n)]
    return lms(l, m)

>>> get_lms(10, 3):
3

n,k=map(int,raw_input().split())
ans=0
for i in range(1,n+1):
    ans=(ans+k)%i
print ans+1

I have tried to implement..bt seems to have high complexity

public static void DeleteM(int[] arr, int m)

    {
        int k = m;
        int count = 0;
        while (count<arr.Length-1)
        {
            if (m < arr.Length && arr[m]!=-1)
            {
                    arr[m] = -1; //Mark it
                    count++;//Set the marked count
                    m = m + k;
            }
            else
            {
                int i = 0;
                if (arr[i] == -1)
                {
                    while (arr[i] == -1 && i < arr.Length)
                    {
                        i++;
                    }
                }
                m = i;

            }

        }
        for(int i=0;i<arr.Length;i++)
            if (arr[i] != -1) Console.WriteLine(arr[i]);
    }

use this function, refer to this answer.

hope it helps.

function removeAtNth($array, $nth)
{
    $step = $nth - 1;       //gaps between operations
    $benchmark = 0;    
    while(isset($array[1]))
    {   
        $benchmark += $step;
        $benchmark = $benchmark > count($array) -1 ? $benchmark % count($array) : $benchmark;
        unset($array[$benchmark]);
        $array = array_values($array);
        echo implode('', $array)."\n";
    }   
}

test:

$array = [1,2, 3,4,5,6,7,8];
removeAtNth($array, 3); 

result:

kris-roofe@krisroofe-Rev-station:~$ php test.php
1245678
124578
24578
2478
478
47
7