Finding a single integer in an array

Question

I'm trying to solve an algorithm question. I need to find a single integer in an array

e.g {1,1,5,5,5,3,2,2}

output should 3 because that's the only single integer there.

So far, I created an algorithm where first I sort the array and then check whether i-1 and i+1 elements are equal and if not it means I've got the single one.

The issue is; for short input it's working fine but for long inputs I receive time-outs (it takes too long to compute so my answer is not validated).

Could you give me any tips for improving the algorithm

static int lonelyinteger(int[] a) {

    Arrays.sort(a);

    if (a.length == 1)
        return a[0];

    for (int i = 0; i < a.length; ++i) {

        if (i == 0) {
            if (a[i + 1] != a[i])
                return a[i];
        } else if (i == a.length - 1) {
            if (a[i] != a[i - 1])
                return a[i];
        } else {
            if (a[i - 1] != a[i] && a[i + 1] != a[i])
                return a[i];
        }  
    }
    return -1;
}

You don't need to sort the array. Iterate through it once, and construct a map of every number you see, and the numbers of times you've seen it. Then just print the numbers with counter == 1. — Traveling Tech Guy
– Traveling Tech Guy, Commented May 19, 2015 at 17:39
The map idea works, but keep in mind that it about triples the memory needed compared to an in-place sort (depending on how many single vs multiple entries there are). For small N that does not matter, but for very large N relative to available memory it would. — Eric J.
– Eric J., Commented May 19, 2015 at 17:40

Shar1er80 · Accepted Answer · 2015-05-19 21:27:37Z

1

Is O(N^2) not considered "fast enough" for this problem?

Here I have a list of 10,000,000 elements with random pair values. In a random spot, I put the "lonely integer" 5, and O(N^2) solves it quickly without the need to sort. The algorithm stops on the first "lonely integer" it finds.

public static void main(String[] args) {
    Random r = new Random();

    List<Integer> ints = new ArrayList<>();
    for (int i = 0; i < 10000000; i += 2) {
        int randomNumber = r.nextInt(100) + 10;
        ints.add(randomNumber);
        ints.add(randomNumber);
    }
    ints.add(5); // Lonely Integer

    int tempIndex = r.nextInt(ints.size());
    int tempValue = ints.get(tempIndex);
    // Swap duplicate integer with lonely integer
    ints.set(tempIndex, ints.get(ints.size() - 1)); 
    ints.set(ints.size() - 1, tempValue);

    for (int i = 0; i < ints.size(); i++) {
        boolean singleInteger = true;
        for (int j = 0; j < ints.size(); j++) {
            if (j == i) {
                continue;
            }
            if (ints.get(j) == ints.get(i)) {
                singleInteger = false;
                break;
            }
        }

        if (singleInteger) {
            System.out.println("Single instance: " + ints.get(i));
            break;
        }
    }
}

Results:

Single instance: 5 (about 10 - 20 seconds);

Update

Your method about 3 seconds.

Map solution...

public static void main(String[] args) {
    Random r = new Random();

    List<Integer> ints = new ArrayList<>();
    for (int i = 0; i < 10000000; i += 2) {
        int randomNumber = r.nextInt(100) + 10;
        ints.add(randomNumber);
        ints.add(randomNumber);
    }
    ints.add(5); // Lonely Integer
    int tempIndex = r.nextInt(ints.size());
    int tempValue = ints.get(tempIndex);
    // Swap duplicate integer with lonely integer
    ints.set(tempIndex, ints.get(ints.size() - 1));
    ints.set(ints.size() - 1, tempValue);

    Map<Integer, Integer> counts = new HashMap<>();
    for (int i : ints) {
        if (counts.containsKey(i)) {
            counts.put(i, counts.get(i) + 1);
        } else {
            counts.put(i, 1);
        }
    }

    for (Integer key : counts.keySet()) {
        if (counts.get(key) == 1) {
            System.out.println("Single Instance: " + key);
        }
    }
}

Results:

Single Instance: 5 (about 1 - 3 seconds)

edited May 19, 2015 at 21:27

answered May 19, 2015 at 19:55

Shar1er80

9,0512 gold badges24 silver badges31 bronze badges

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

8 Comments

Shar1er80 Over a year ago

@sodium24 Yeah... I retracted my update of finding multiple "lonely integers" after putting random pairs of numbers vs all the same number. Afterwards I wanted to make sure that finding the first "lonely integer", inside of random pairs, still held up and it did.

waff Over a year ago

sorry for the noob question I'm studying algorithms and I didn't really understand how to calculate time complexity but, I think my current solution has O(n*logn) complexity, isn't O(N^2) worse than that.

Shar1er80 Over a year ago

@waff Yes... O(N * logN) is faster than O(N^2), but is your algorithm really O(N * logN), since you're calling Arrays.sort(a)?

waff Over a year ago

Arrays.sort is a quick sort method and it is O(n log(n)) on avarage. At least that's what google says. But again I'm no expert. bigocheatsheet.com docs.oracle.com/javase/7/docs/api/java/util/…

Shar1er80 Over a year ago

@waff Yes, I read that too, but then you're doing an O(n) search after O(N * logN) sort. The two combined are still faster than O(n^2)? I'm still learning O notation also.

|

Stanislav · Accepted Answer · 2015-05-19 18:40:28Z

1

Are you sure you got the question right? The idea behind the lonely integer algorithm question, which is commonly posted on algorithm solving challenges, is that all numbers show up in pairs, except for one. From the sample that you used, it is not the case.

If all numbers are being displayed in pairs, except for one, the fastest way to find the solution is by applying XOR on all elements. Since XOR applied between two same elements cancels them, you will as a result have the lonely integer that you are looking for. The time complexity for this solution would be O(n).

Otherwise, if a number can be found in the given array more than two times, or you are using the solution you provided, the time complexity is O(n*logn).

answered May 19, 2015 at 18:40

Stanislav

11010 bronze badges

2 Comments

waff Over a year ago

the question is right. I'm simply asking if there's any way to improve the solution so it could work a bit faster than it is now.

Stanislav Over a year ago

Sorry for the misdirection, in that case.

Jihed Amine · Accepted Answer · 2015-05-19 21:21:35Z

1

Start by checking that it's not Arrays.sort(a); that's taking too long for very large inputs.

If it's not the case, you could improve your method as follows

 static int lonelyinteger(int[] a) {
    if (a[0] != a[1]) return a[0];

    int i = 1;
    while ((i < a.length - 1) && (a[i] == a[i-1] || a[i] == a[i+1])) {
        i++;
    }

    if ((i < a.length -1) || (a[i] != a[i-1]))  return a[i];
    return -1;
}

answered May 19, 2015 at 21:21

Jihed Amine

2,20820 silver badges32 bronze badges

Comments

marcomarandiz · Accepted Answer · 2015-05-19 22:41:44Z

0

sort. then...

while (true) {
    if (a[0] != a[1]) {
        return a[i].
  } else {
      remove all a[0]s from a.
  }
}

this is O(nlogn).

an O(n) solution (one w/o sort) to find all the unique integers is to have a hash and run along the array. If the number does not appear in the hash, add the number to it. If it does appear in the hash, remove that number from the hash. At the end you'll have all the unique integers in one hash. boom.

edited May 19, 2015 at 22:41

answered May 19, 2015 at 18:28

marcomarandiz

1175 bronze badges

Collectives™ on Stack Overflow

Finding a single integer in an array

4 Answers 4

Update

8 Comments

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Update

8 Comments

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related