Code to check to check duplicate elements and return true if there a duplicate elements and false if not.

bool containsDuplicate(int *a, int n) {
    for (int i = 0; i < n; i  ) {
        int element = a[i];
        for (int j = i   1; j < n; j  ) {
            if (a[j] == element) {
                return true;
            }
        }
    }
    return false;
}

I thought it is correct code but it is showing a time limit exceeded error.

CodePudding user response：

to reduce time complexity of given code?

OP's approach is O(n*n)

Below is an O(n*log n) approach.

1. Copy array a to a new array b

2. Sort b with qsort()

3. Walk b looking for adjacent repeats.

CodePudding user response：

Well, if you have the memory...

Assuming 4 bytes int (which is common) you can do it in O(N) by using half a giga byte dynamic memory. It's done by making an array of unsigned char and let each bit represent an int value.

Something like:

#include <stdio.h>
#include <stdlib.h>

int containsDuplicate(int *a, int n)
{
  int res = 0;
  size_t sz = (1ULL << 32) / 8;  // or just (1ULL << (32-3))
  unsigned char* p = calloc(sz, 1);
  if (!p) exit(1);

  for (size_t i = 0; i < n;   i)
  {
    unsigned int u = a[i];
    unsigned int idx = u / 8;
    unsigned int bit = u % 8;
    unsigned char v = p[idx];

    if (((v >> bit) & 0x1) != 0)
    {
      res = 1;
      break;
    }
    p[idx] |= (1 << bit);
  }
  free(p);
  return res;
}


int main()
{
  int arr[] = {435435, 7657, 43243, 435435, 989723};
  size_t sz_a = sizeof arr / sizeof arr[0];

  if (containsDuplicate(arr, sz_a))
  {
      puts("Duplicate found");
  }
  else
  {
    puts("No duplicate found");
  }

  arr[3] = 42;

  if (containsDuplicate(arr, sz_a))
  {
      puts("Duplicate found");
  }
  else
  {
    puts("No duplicate found");
  }

  return 0;
}

Output:

Duplicate found
No duplicate found