My for loop is adding 1 excess and i do not know why-CodePudding

Basically im trying to make a program that loops through the given array, and checks if the right element is 2x bigger than the left one, if true inserts average value of those two elements in the middle. After that, it prints out the array with inserted elements, and then loops through the array again, counting how many times a certain number appears. I coded all of it successfully using pen and paper and writing the problem into smaller chunks and then coding it in C but the problem is when i enter 100 zeros (one hundred zeros). the program prints out that the number 0 is repeated 200 times instead of 199. I do not know why. And sorry for the code being bad, my current task is to get good at solving problems with pen and paper, after i become decent at that and develop my logic, i will try making the code simpler.

Input sample: 
Enter the number of elements: 100
Enter the array: 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
After adding middle element: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002.33412e-310 
The number is repeated 200 time/s

My code

#include <math.h>
#include <stdio.h>

#define EPSILON 0.0001

int main() {
  int n, i, j, k, digit, length = 0, digit_array[10] = {0};
  double array[200], temp;
  do {
    printf("Enter number of elements: ");
    scanf("%d", &n);
  } while (n <= 0 || n >= 101);

  printf("Enter elements: ");

  length = n;

  for (i = 0; i < length; i  )
    scanf("%lf", &array[i]);

  for (i = 0; i < length; i  ) {
    temp = array[i]   array[i];
    if (fabs(temp - array[i   1]) < EPSILON) {
      for (j = length; j > i   1; j--)
        array[j] = array[j - 1];
      array[i   1] = (array[i]   array[i   1]) / 2.;
      i  ;
      length  ;
    }
  }

  printf("After adding middle element: \n");
  for (i = 0; i < length; i  )
    printf("%g ", array[i]);

  for (i = 0; i < length; i  ) {
    temp = array[i];
    digit = ((int)(temp * 10)) % 10;
    digit_array[digit]  ;
  }
  printf("\n");

  for (i = 0; i < 10; i  ) {
    if (digit_array[i] != 0)
      printf("Number %d is repeated %d time/s.\n", i, digit_array[i]);
  }

  return 0;
}

CodePudding user response：

Rather than constantly shifting the array, it's a lot easier and faster to use two arrays. All you need is this:

// Inputs:
//   n: The number of inputs.
//   a: An array of at least n doubles containing the inputs.
//   b: An array of at least n*2-1 doubles that will containing the outputs.

// Outputs:
//   m: The number of outputs.
//   b: An array of at least m doubles containing the outputs.

size_t i = 0;
size_t j = 0; 

double prev = b[j  ] = a[i  ];

while (i < n) {
   double next = a[i];
   if (fabs(prev*2 - next) < EPSILON) {   // If a[i-1] exactly equal a[i]*2.
      b[j  ] = next / 2.0   prev / 2.0;   // Or: b[j  ] = prev * 1.5;
   }

   prev = b[j  ] = a[i  ];
}

size_t m = j;

Regarding prev * 1.5:

average(next, prev)
= ( next   prev ) / 2
= ( prev * 2   prev ) / 2
= ( prev * 3 ) / 2
= prev * 1.5

Included in a proper function:

int f(double *a, size_t n, double **b_ptr, size_t *m_ptr) {
   double b = malloc( (n*2-1) * sizeof(double) );  // We need up to this much.
   if (b == NULL) {
      *b_ptr = NULL;
      return 0;
   }

   size_t i = 0;
   size_t j = 0; 

   double prev = b[j  ] = a[i  ];

   while (i < n) {
      double next = a[i];
      if (fabs(prev*2 - next) < EPSILON) {   // If a[i-1] exactly equal a[i]*2.
         b[j  ] = next / 2.0   prev / 2.0;   // Or: b[j  ] = prev * 1.5;
      }

      prev = b[j  ] = a[i  ];
   }

   b = realloc(b, j * sizeof(double));  // Free the excess. (Optional)
   size_t m = j;

   *b_ptr = b;
   *m_ptr = m;
   return 1;
}