Meena - 1 year ago 64
C Question

# Find the duplicate element from an integer

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;
}
``````

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
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download