Janusz Waligóra - 3 months ago 22

C Question

As input I recive a list of natural integers.

I have to store them inside a structure that enables me to go from the last element to the first without much problem.

The task is to perform t (number given from the start) operations on this data structure. Starting from the first number given as input (i=0):

If data[i] % 2 == 0 -> perform operation R

else -> perform operation X

operation R: remove element with index position i+1, and move to the right as many times as was the value of removed element.

operation X: take the value of data[i] element and insert new element in front of that one with value data[i]-1. Then move data[i] times to the right.

example (i->n means that i points to el. with value n):

input: 3 1 2 3

t = 3

data = [ 1, 2, 3 ]

`1.`

i->1

operation X,

result: [ 1, 0, 2, 3 ]

2.

i->0

operation R,

result: [ 1, 0, 3 ]

3.

i->1

operation X,

result: [ 1, 0, 0, 3 ]

The real problem occurs when the value of t is very large.

I tried two implementations:

- One based on linked list. I know it works because the result is correct, but execution time is close to 2-3 minutes.
- One based on an array but the execution time is just a little faster.

Here is the fragment that takes 99,99% of execution time:

`while(t--){`

c = current -> value;

if(c % 2 == 0){

c = current -> next -> value;

Node* n = current -> next -> next;

free(current -> next);

current -> next = n;

--size;

}

else{

Node* n = getNode(current -> next);

current -> next = n;

n -> value = c-1;

++size;

}

c %= size;

while(c--){

current = current->next;

}

}

getNode(Node* n) returnes new node with node -> next = n.

Any insight into optimalization method/ other approach appreciated.

*edit:

`Node* getNode(Node* nxt){`

Node* first = (Node*)malloc(sizeof(Node));

first -> value = -1;

first -> next = nxt;

return first;

}

Answer

Thinking in terms of the algorithm run-time (where n is the length of elements):

- You need
`t`

operations, so outside loop is`O(n)`

- If you use linked lists, finding ith element is
`O(n)`

and moving the`ith`

element around is`Theta(1)`

as you are just changing the pointers making your inner while loop`O(n)`

so total runtime of`O(n^2)`

- With array, finding ith element is
`Theta(1)`

but moving them around is`O(n)`

, so inner loop is again`O(n)`

, total being`O(n^2)`

Can you use a hashmap with integer index as the key and value working as if it's a linked list? Hashmaps will make both the search and move `Theta(1)`

making the total `O(n)`