Meena Meena - 1 month ago 5
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;
}

Answer

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
Comments