How to start from the position of an element you remove

Question

I am doing some interview prep and working on this leetcode question I came across. The questions states Given two integers m and n, loop repeatedly through an array of m and remove each nth element. Return the last element left. (If m = 7 and n = 4, then begin with the array 1 2 3 4 5 6 7 and remove, in order, 4 1 6 5 2 7 and return 3.). From my work it looks like 7 will be the last number not 3.

My thought process was to add all the elements in a ArrayList or LinkedList and then use the remove() function to get rid of the position thats passed. What I would like to know is how can I start from the element I remove and just add that many indexes and remove the next number? I have my code down below.

static int arraryReturn (int [] a, int b, int c) {
    LinkedList<Integer> myList = new LinkedList<>();
    for(int i =0; i< a.length;i++) {
        myList.add(i);
    }


    while(myList.size() > 0) {
        myList.remove(c);

    }



    return -1;
}

I never wrote it down. I had it saved in eclipse and decided to work on it. — Mohamed Ali, Sep 22 '18 at 21:33
To answer the question in your title: you cannot do it with the built-in linked list. You would either need to calculate the total index (current + step) and use that with the `remove` method (although it would be quadratic time) or implement your own linked list to have full control over the implementation details — Dici, Sep 22 '18 at 23:02
What does `int[] a` represent ? what does `b` and `c`? you should specify clearly. From problem description it seems you only need two integers `m`, `n` as input. — SomeDude, Sep 22 '18 at 23:06
@SomeDude he also needs a set of values though. They don't necessarily have to be `1...m`. — Dici, Sep 22 '18 at 23:07
@moeeli actually you could use an `Iterator` and use `Iterator.remove`. — Dici, Sep 22 '18 at 23:09
@Dici I know it need not be a list like `1...m`, it can be just an `m` but why does he need an array `a` and then two integers `b` and `c`? there is something incomplete with description. — SomeDude, Sep 22 '18 at 23:10
This is known as the [Josephus problem](https://en.wikipedia.org/wiki/Josephus_problem). There's an explicit formula for computing the index of the last remaining element for the case n==2. For the general case, there's a recursive relation to compute the index that runs in O(m) and, for m >> n, a different relation to compute the index in O(n log m) time. See [this question](https://stackoverflow.com/questions/31775604/explanation-for-recursive-implementation-of-josephus-prob). — Ted Hopp, Sep 23 '18 at 00:44

Dici · Accepted Answer · 2018-09-23T19:09:06.580

Decently fast solution using a bit of memory to maintain a graph of nodes and avoid traversing n elements at every step. I think the complexity is O(m), although I haven't proved it rigorously.

public static void main(String[] args) {
    List<Integer> values = Arrays.asList(1, 2, 3, 4, 5, 6, 7);
    int m = values.size(), n = 4;

    Node[] nodes = initializeGraph(values, m, n);

    Node current = nodes[0];
    for (int i = 0; i < m - 1; i++) {
        Node out = current.out;
        out.remove();
        current = out.right;
    }
    System.out.println(current.value);
}

private static Node[] initializeGraph(List<Integer> values, int m, int n) {
    Node[] nodes = new Node[m];

    for (int i = 0; i < m; i++) nodes[i] = new Node(values.get(i));
    for (int i = 0; i < m; i++) {
        Node current = nodes[i];

        current.right = nodes[(i + 1) % m];
        current.left = nodes[(m + i - 1) % m];
        Node next = nodes[(i + n) % m];

        current.out = next;
        next.addIn(current);
    }

    return nodes;
}

private static class Node {
    private final int value;
    private final Set<Node> in = new HashSet<>();

    private Node out;
    private Node left;
    private Node right;

    public Node(int value) {
        this.value = value;
    }

    public void addIn(Node node) {
        in.add(node);
    }

    public void remove() {
        left.right = right;
        right.left = left;

        for (Node node : in) {
            node.out = right;
            right.addIn(node);
        }

        out.in.remove(this);
    }
}

How to start from the position of an element you remove

1 Answers1