Finding duplicate elements in an array without using nested loops

Question

I recently had an interview which consisted of following problem. Please help with possible solutions.

Write a method in Java to find duplicate elements in an integer array without using nested loops ( for/ while / do while, etc ) and without using library functions or standard API's.

@DevChoudhary Did the interviewer say you can't use loops at all or just that you can't nest loops? — Chetan Kinger, Jul 18 '15 at 06:51
Very similar: http://stackoverflow.com/questions/14944458/find-duplicate-element-in-array-in-time-on — fhissen, Jul 18 '15 at 07:04
How is this a duplicate of the question indicated above? This question asks for all duplicate elements, the question tagged as duplicate asks only for an element. Very clear distinction between the two. — Rahul Prasad, Jul 19 '15 at 08:15

score 1 · Answer 1 · answered Jul 18 '15 at 06:43

1

Hey the below solution has complexity O(n) and works fine. Check if it helps.

public class Main {
    public static void main(String[] args) {
        int a[] = new int[]{10,3,5,10,5,4,6};
        String distinctElement="";
        String repetitiveTerms="";
        for(int i=0;i<a.length;i++){
            if(i==0){
                distinctElement+=a[i]+" ";
            }
            else if(distinctElement.contains(""+a[i])){
                repetitiveTerms+=a[i]+" ";
            }
            else{
                distinctElement+=a[i]+" ";
            }
        }

    }
}

answered Jul 18 '15 at 06:43

Kulbhushan Singh

627
4
20

What part of *without using nested loops ( for/ while / do while, etc )* said that you could use loops? – Chetan Kinger Jul 18 '15 at 06:44
It's not much of a challenge if you can use loops. My understanding of the question is that you can't use loops. Let's wait for the OP to clarify. – Chetan Kinger Jul 18 '15 at 06:50
1

i think loops are allowed but not nested – Madhawa Priyashantha Jul 18 '15 at 06:51
Ok that's fine but "NESTED" is clear to us right. So you should not downgrade the answers unless you are sure about it – Kulbhushan Singh Jul 18 '15 at 06:52
@Fast Snail : No it won't be problem. If you will see the code carefully i have inserted spaces between the elements so 1 0 cannot be 10. I hope this clarifies. – Kulbhushan Singh Jul 18 '15 at 06:59
@KulbhushanSingh oops i didn't see that.good – Madhawa Priyashantha Jul 18 '15 at 07:01
@Fast Snail : That's ok :) – Kulbhushan Singh Jul 18 '15 at 07:02
I think this will fail if the array has negative values, eg: `"0 -1 5".contains("1") == true` or values with different scale eg: `"100 20".contains("10") == true` – Titus Jul 18 '15 at 07:05
Yeah that will fail. What could be the probable solution @Titus – Kulbhushan Singh Jul 18 '15 at 07:14
I think `distinctElement.contains(" "+ a[i] + " ")` will partially fix that (it won't check the last added element because the `distinctElement` doesn't terminate with a space, eg: `"10 20 30".contains(" 30 ") == false`). – Titus Jul 18 '15 at 07:15
I very much doubt that this has O(n) complexity, as `contains` is just another loop. Also i'd argue it doesn't fulfill the not library functions part. – MikeMB Jul 18 '15 at 07:42
loops can be used , but not nested ones – Dev Choudhary Jul 18 '15 at 08:42
@Dev See if you the above logic helps... – Kulbhushan Singh Jul 18 '15 at 09:09

Finding duplicate elements in an array without using nested loops

1 Answers1