How to improve performance in this code

Question

I made the point The Legend of Flavious Josephus, but the time limit has expired, which I can change to decrease the time

My code

#include <stdio.h>

void carregaVetor(int *vetor, int numero);
void removeNum(int *vetor, int *cont, int *tam, int *indice);
void removeElem(int *vetor, int *posicao, int *tam, int *cont);  
int main(int argc, char** argv)
{

int vetor[90000], cont = 0, tam, indice = 0, posi;
int teste, numero, pulo, i;
while(scanf("%d", &teste) != EOF)
{
    for(i = 0; i < teste; i++)
    {
        scanf("%d %d", &numero, &pulo);
        tam = numero;
        carregaVetor(vetor, numero);
        while(tam != 1)
        {
            cont = posi = indice = 0;
            while(indice != (pulo - 1))
            {
                removeNum(vetor, &cont, &tam, &indice);
            }
            cont = 0;
            while(cont != pulo)
            {
                removeElem(vetor, &posi, &tam, &cont);
            }
        }
        printf("Case %d: %d\n", i + 1 , vetor[0]);
    }
}

  return 0;
}

 void carregaVetor(int *vetor, int numero)
{
   int i;
  for(i = 0; i < numero; i++)
  {
      vetor[i] = i + 1;
  }
}

 void removeNum(int *vetor, int *cont, int *tam, int *indice)
{
   (*tam)++;
   vetor[*tam] = vetor[*indice];
   (*cont)++;
   (*indice)++;
}

 void removeElem(int *vetor, int *posicao, int *tam, int *cont)
{
   int i;
   for(i = (*posicao); i < (*tam); i++)
   {
       vetor[i] = vetor[i + 1];
   }
   (*tam)--;
   (*cont)++;
}

Answer 1

To analyze this code, let’s apply some transformations:

1. Correct the indentation.

2. Put variable statements in the smallest possible scope.

   • The variable tam can be stated where she receives numero. And that statement may be moved to stand immediately before the while (tam != 1).

   • The variables numero and pulo may be declared immediately before the scanf who reads them.

   • The variable indice can be declared at the place where zero is assigned to it.

   • The variables i may be declared in for where they are used.

   • The variable posi is used only in while of removeElem. Its value is always set to zero before this while be executed. Soon, we can move your statement to stand immediately before that while. Thus, the while gets like this:

     int posi = 0;
     while (cont != pulo) {
         removeElem(vetor, &posi, &tam, &cont);
     }
     

   • The variable cont is set to zero before the while of removeNum where it is used and set to zero again before the while of removeElem where it is used. This way, we can exchange for two different variables declared each before their respective while.

     int indice = 0, conta = 0;
     while (indice != pulo - 1) {
         removeNum(vetor, &conta, &tam, &indice);
     }
     
     int contb = 0, posi = 0;
     while (cont != pulo) {
         removeElem(vetor, &posi, &tam, &contb);
     }
     

3. We can copy and paste the function body removeElem, removeNum and carregaVetor back to main to facilitate our analysis and disassembly of the code. The variables i of carregaVetor and of removeElem are renamed to j not to collide with the i already existing in the main. Pointer references and references are deleted. The result so far is this:

           for (int j = 0; j < numero; j++) {
               vetor[i] = j + 1;
           }
           int tam = numero;
           while (tam != 1) {
               int indice = 0, conta = 0;
               while (indice != pulo - 1) {
                   tam++;
                   vetor[tam] = vetor[indice];
                   conta++;
                   indice++;
               }
               int contb = 0, posi = 0;
               while (contb != pulo) {
                   for (int j = posi; j < tam; j++) {
                       vetor[j] = vetor[j + 1];
                   }
                   tam--;
                   contb++;
               }
           }
   

4. Note that the variable posi always has the value zero. In fact, the function removeElem read its value from its address, but never write on it. So, you can delete this variable.

5. Note that the variable conta (which is the cont of its original code when used in while of removeNum) always has the same value of indice and that its value is never used for anything. Therefore, it can be eliminated.

6. We can rewrite both whiles above (those of removeElem and of removeNum) as ties for. The first uses the variable indice as an accountant and the second uses contb.

7. Your while (scanf("%d", &teste) != EOF) will only be (or should be) executed once. In this case, it is not necessary to use while, just use the scanf alone. Your problem also does not need to consider malformed entries where the number of the NC of the problem statement would not be informed or something like that, so you do not need to check the return of the scanf.

8. Your while (tam != 1) is like this:

       while (tam != 1) {
           for (int indice = 0; indice != pulo - 1; indice++) {
               tam++;
               vetor[tam] = vetor[indice];
           }
           for (int contb = 0; contb != pulo; contb++) {
               for (int j = 0; j < tam; j++) {
                   vetor[j] = vetor[j + 1];
               }
               tam--;
           }
       }
   

   • Note that the tam++ will be executed a number of times that is exactly pulo - 1. Soon, you can put one tam += pulo - 1 after this for and replace vetor[tam] for vetor[tam + indice].

   • The variable tam is decreased whenever contb is incremented. At this point it is possible to conclude that it will be decremented contb times and it is possible to put tam -= pulo after the for of contb. The value of tam in the loop of j can be replaced to tam - contb. Right now we’ll have it in the code:

         tam += pulo - 1;
         for (int contb = 0; contb != pulo; contb++) {
             for (int j = 0; j < tam - contb; j++) {
                 vetor[j] = vetor[j + 1];
             }
         }
         tam -= pulo;
     

   • We can then change the tam of the tie of j for tam + pulo - 1, eliminate the tam += pulo - 1; and change the tam -= pulo; for tam--;.

   • With that, we can finally exchange the while (tam != 1) by a noose for.

The resulting code is thus:

#include <stdio.h>

int main(int argc, char** argv) {
    int vetor[90000];
    int teste;
    scanf("%d", &teste);
    for (int i = 0; i < teste; i++) {
        int numero, pulo;
        scanf("%d %d", &numero, &pulo);
        for (int j = 0; j < numero; j++) {
            vetor[j] = j + 1;
        }
        for (int tam = numero; tam != 1; tam--) {
            for (int indice = 0; indice != pulo - 1; indice++) {
                vetor[tam + indice] = vetor[indice];
            }
            for (int contb = 0; contb != pulo; contb++) {
                for (int j = 0; j < tam + pulo - 1 - contb; j++) {
                    vetor[j] = vetor[j + 1];
                }
            }
        }
        printf("Case %d: %d\n", i + 1, vetor[0]);
    }

    return 0;
}

Looking at the resulting code, we see that it has a high complexity because we have a for within a for within a for within a for. The operation that is executed a greater number of times is the vetor[j] = vetor[j + 1]; which is intended to remove an element from the middle of the vector and displace all subsequent elements. In the indice, the instruction vetor[tam + indice] = vetor[indice]; is also deleting elements from the vector medium.

Vectors are not structures that rely on removing elements in the middle as an efficient thing to do, and so it would be best if you looked for a data structure that has such a feature, which suggests that the ideal solution would be made through dynamically linked lists (and perhaps circular).