-1

Given a list of numbers, such that all but one element occurs more than once in the list. Find the element that occurs only once.

This is Java implementation:

package competitiveprograming;
import java.util.*;

public class FindSingleInArray {

    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        System.out.print("Enter size of array");
        int size=sc.nextInt();
        System.out.print("Enter an element where one of the element will not repeat again..");
        int arr[]= new int[10];
        for(int i=0;i<size;i++)
        {
            arr[i]=sc.nextInt();
        }

        List<Integer> no_duplicate_list= new ArrayList<Integer>();

        for(int j : arr)
        {
            if(!no_duplicate_list.contains(j))
            {
                no_duplicate_list.add(j);
            }
            else
            {
                no_duplicate_list.remove(j);
            }
        }

        System.out.print(no_duplicate_list.get(0));
        sc.close();
    }
}

And this is the error message I'm getting:

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 2 out of bounds for length 1
    at java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:64)
    at java.base/jdk.internal.util.Preconditions.outOfBoundsCheckIndex(Preconditions.java:70)
    at java.base/jdk.internal.util.Preconditions.checkIndex(Preconditions.java:248)
    at java.base/java.util.Objects.checkIndex(Objects.java:373)
    at java.base/java.util.ArrayList.remove(ArrayList.java:502)
    at competitiveprograming/competitiveprograming.FindSingleInArray.main(FindSingleInArray.java:28)
Alexei Levenkov
  • 98,904
  • 14
  • 127
  • 179
Raviteja
  • 3
  • 2

4 Answers4

2

If I understand you correctly, you are trying to find all elements in the input array which were NOT repeated.

So if this is the input array:

1 2 2 3 3 3 4

The output should look like this:

1 4

But your code will produce this because every uneven time the number appears it will add it to the no_duplicate_list again:

1 3 4

This is however not the reason for your exception. The reason for the exception is because you are passing an int j to List.remove(int position) and it tries to remove the element at position j, and not the element with value of j. To fix this you need to cast your int into Integer before removing it from the list, this way you are calling List.remove(Integer object).

no_duplicate_list.remove((Integer)j);
HomeIsWhereThePcIs
  • 1,273
  • 1
  • 19
  • 37
0

The error you are getting is a "IndexOutOfBoundsException" error. This comes when you try to read or change something outside the bound of an array. Example: If you have an array of size 4 and you try to read any element beyond the size like arrayName[7], you get this error.

In your case your code makes this error because you call remove no_duplicate_list.remove(j);. Remove is an overloaded function and can both take an element of the type in the list or take an index. It looks like you are trying to use the first one, but because you are passing the argument as an int, it uses the second function. This tells the code to remove an element at a certain position that is out of bounds of the list.

Pete
  • 569
  • 3
  • 9
  • 1
    This does not address a possible solution. – MikaelF Apr 04 '20 at 23:43
  • You are right. I am guessing @HomeIsWhereThePcIs's solution will work for that, but I have not tested that. But he did ask for an explanation of the error. – Pete Apr 04 '20 at 23:49
  • 2
    For posterity's sake, your edit fixed it, and my previous comment is no longer relevant. – MikaelF Apr 04 '20 at 23:51
0

Your problem is that you call no_duplicate_list.remove(j); but j is supposed to be an index not a value. See the official docs.

Another possible future bug is the logic of your code on the following input:

1, 2, 1, 2

the first two numbers will be added to the list but the third number (1) is already in the list, so it will be deleted (if you fix the issue with passing index to remove() method instead of value). Same applies to the forth number 2. The result is an empty list instead of list of two values 1, 2.

There are two simple solutions:

  1. Change List to Set which by its implementation ignores duplicates.
  2. Just remove the part of the code of removing the element.

My personal advice is option 1, if you don't want duplicates, just don't use List object and use something that Java has already prepared for your problem.

Lkopo
  • 4,798
  • 8
  • 35
  • 60
  • `ArrayList.remove()` does not throw an `IndexOutOfBoundsException` if the element is not already present, only if the index is, well, out of bounds. See the [javadoc](https://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html#remove(int)). I agree that using a `Set` is a more robust solution, but it only sidesteps the issue, and doesn't address why the exception is raised in the first place. – MikaelF Apr 04 '20 at 23:48
  • 1
    Updated the answer, yes I believe that the problem is that OP is passing value to `List.remove()` instead of index of that value and that causes `IndexOutOfBoundsException`. Even stack trace says that it fails on remove method. – Lkopo Apr 04 '20 at 23:51
0

The reason for IndexOutOfBounds is answered already. The logic for the actual problem is incorrect.

Consider 1,1,1,2,2,3 as an example. Initially, 1 is added to no_dup and then it will be removed next and again 1 will be added in third iteration. The final result will have 1&3, but ideally, the answer should be 3.

Using HashMaps should be quick even if the input is large.

Kali
  • 16
  • 1