Find duplicates in array without extra memory and can use variables for storing values

Question

How can we find the duplicate elements in an array with the following limitations:

Without using extra memory
Can use variables for storing data and not objects like HashMap/HashSet and all.
Time complexity can be O(n) and should not be O(n^2)

Note :

Here array is dynamic integer array.

We cannot. Sorry.

n. m. could be an AI
– n. m. could be an AI

2017-09-09 03:25:05 +00:00
Commented Sep 9, 2017 at 3:25 — n. m. could be an AI
– n. m. could be an AI, Commented Sep 9, 2017 at 3:25

marvel308 · Accepted Answer · 2017-09-09 06:59:47Z

1

If all elements of the array are in between [0, n), then we can do it in the following way

Traverse the array from i = 0 to n
for every element a[i], suppose

x = a[i] if a[i] >= 0
x = a[i] + n if a[i] < 0
check if a[x] >= 0. If yes then add -n to a[x]
if for another element a[i]. if a[x] < 0 then that means that a similar value changed the index hence it is a duplicate.

answered Sep 9, 2017 at 6:59

marvel308

10.5k3 gold badges24 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Yan Khonski Over a year ago

But a[i] >= 0. As you stated before. So you never add n.

marvel308 Over a year ago

I am adding -n to a[x] so it can become negative

Santhosh Surimani Over a year ago

Provided solution will work only If all elements of the array are in between [0, n], if not it will throw an ArrayIndexOutOfBoundsException.

Santhosh Surimani · Accepted Answer · 2018-04-27 05:29:16Z

0

Below is my solution for the above question.

public static boolean checkDuplicates(int[] arr, int length) {
    int value = 0;
    boolean isDupFound = false;
    for (int i = 0; i < length; i++) {
        int currChar = arr[i];
        int bit_Position = currChar - 'a';
        if ((value & (1 << bit_Position)) > 0) {
            isDupFound = true;
            break;
        } else {
            value = value | (1 << bit_Position);
        }
    }
    return isDupFound;
}

answered Apr 27, 2018 at 5:29

Santhosh Surimani

939 bronze badges

3 Comments

Gulzar Over a year ago

That doesn't answer your own question. You wanted to find "the duplicate elements in an array", which you did not accomplish here.

Santhosh Surimani Over a year ago

Hi Gulzar.. Here we just need not to break the loop if we found the duplicate element in array and continue till all the elements in an array which will serve our purpose.

Santhosh Surimani Over a year ago

Remove the break and print all the values instead to assign to a boolean value.

Collectives™ on Stack Overflow

Find duplicates in array without extra memory and can use variables for storing values

2 Answers 2

3 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related