CODEWITHSUNDEEP
javaarraysalgorithm
waff
waff

Reputation: 51

Finding a single integer in an array

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;
}

Upvotes: 4

Views: 2096

Answers (4)

marcomarandiz
marcomarandiz

Reputation: 117

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.

Upvotes: 0

Shar1er80
Shar1er80

Reputation: 9041

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)

Upvotes: 1

Jihed Amine
Jihed Amine

Reputation: 2208

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;
}

Upvotes: 1

Stanislav
Stanislav

Reputation: 110

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).

Upvotes: 1

Related Questions