Meena - 9 months ago 39

C Question

Last week I attended interview. They asked a question for finding a duplicate element in integer value.I know program using array but they asked to me without array. Please help me for finding duplicate element in integer without array.

Question:

**Find the duplicate element from an integer display the element without the duplicate number. Like I/P:43456 O/P:4356. Condition: no array should be used**

Coding:

`void printRepeating(int arr[], int size) {`

int i;

printf("The repeating elements are: \n");

for (i = 0; i < size; i++) {

if (arr[abs(arr[i])] >= 0)

arr[abs(arr[i])] = -arr[abs(arr[i])]; elseprintf(" %d ", abs(arr[i]));

}

}

int main() {

int arr[] = { 1, 2, 3, 1, 3, 6, 6 };

int arr_size = sizeof(arr) / sizeof(arr[0]);

printRepeating(arr, arr_size);

getchar();

return 0;

}

Answer Source

This is a rough sketch:

For each integer in the input, traverse the input towards the beginning, and compare each integer to the current one. If there is a match, move on to the next input integer. If you reach the beginning, it isn't a duplicate, so print it.

```
void printRepeating(const int arr[], size_t size) {
const int* begin = arr;
const int* end = arr + size;
if ( begin == end ) return;
// First element cannot be a duplicate, so always print it
std::cout << *begin;
// Traverse input array
const int* curr = begin;
while ( ++curr < end ) {
// Traverse back to find a duplicate
const int* curr_rev = curr - 1;
for ( ; curr_rev >= begin && *curr != *curr_rev; --curr_rev );
if ( curr_rev < begin )
// Reached the beginning, so it cannot be a duplicate
std::cout << " " << *curr;
}
}
```

And while I'm not sure, whether constructing a pointer to the element just before an array is undefined behavior, here is a slight variation, that traverses the input from front to back to find a duplicate. This is just the main loop - everything else like above:

```
// Traverse input array
const int* curr = begin;
while ( ++curr < end ) {
// Traverse again to find a duplicate
const int* cmp = begin;
for ( ; cmp < curr && *cmp != *curr; ++cmp );
if ( cmp == curr )
// Reached current integer, so it cannot be a duplicate
std::cout << " " << *curr;
}
```

Given this program:

```
int main() {
const int arr[]{ 1, 2, 3, 1, 3, 6, 6 };
printRepeating( arr, std::end( arr ) - std::begin( arr ) );
}
```

produces the following output:

`1 2 3 6`