How do I further optimize my code?

Question

I'm given an array of doubles, all numbers are equal except for one. My task is to find that unique number. My code returns the correct output and now I'm wondering how will I further optimize it.

This is my code:

public static double findUnique(double array[]) {
    double unique = 0;
    double common = 0;

    for(int i=0; i<array.length; i++) {
        for(int j=i+1; j<array.length; j++) {
            if(array[i]==array[j]) {
                common = array[i];
            }
        }
        if(common!=array[i]) {
            unique = array[i];
        }
    }
return unique;  
}

The only thing I could think of is storing the length of the array first, but after some testing it actually took longer. Thanks.

Okay, now I feel dumb for not testing this. I used `break` in the `if` statements and it significantly reduced the time needed. I'm still open to answers though. — Helquin, Aug 28 '17 at 08:55
Really easy. Look at `array[0]`, `array[1]`, `array[2]`. If any of them is different from the others, return the unique one. If all are the same, search in `array[3...N-1]` for the one element that is **not** equal to `array[0]`. — Iwillnotexist Idonotexist, Aug 28 '17 at 08:56
@IwillnotexistIdonotexist thanks for the suggestion, I'll make a new method based on this. — Helquin, Aug 28 '17 at 09:07

Slava Vedenin · Accepted Answer · 2017-08-28T09:08:42.717

3

public static double findUnique(double array[]) {
    if(array.length < 3) { 
       throw new IllegalArgumentException("wrong array");
    }

    double common;
    if(array[0] == array[1]) {
       common = array[0];
    } else {
       return array[0] != array[2]? array[0]: array[1];
    }

    for(int i=2; i<array.length; i++) {
       if(common != array[i]) {
          return array[i];
       }
    }
    throw new IllegalArgumentException("wrong array"); 
}

edited Aug 28 '17 at 09:08

answered Aug 28 '17 at 09:03

Slava Vedenin

58,326
13
40
59

That `if(array.length<3)` part seems to be made for the codewars kata. Still it's better than my code. – Helquin Aug 28 '17 at 09:13
If if(array.length<3) not need, you can just not use it. i write it for general case, when possible to have wrong argument. – Slava Vedenin Aug 28 '17 at 09:21
Sorry for the remark, I just realized that an array with a length less than 3 and having only two different elements would never have a unique nor common element. – Helquin Aug 28 '17 at 09:24
Anyone taking arr.Length in a variable before the loop like int arrLen = array.length; That would optimize it further. – Amit Kumar Singh Aug 28 '17 at 09:36
1

@Amit : I beleive that is a theoretical gain, not a practical one (at least in my benches it is). See also : https://stackoverflow.com/questions/1208320/what-is-the-cost-of-calling-array-length – GPI Aug 28 '17 at 10:07

Axiomel · Answer 2 · 2017-08-28T09:39:35.837

I belive that it is uneccesary to grab two new numbers in everey iteration.

Instead we could just start by grabbing the two first numbers of the array and then if those numbers are the same, we may compare the rest of the numbers to their value. So we define our common above the for loops, that way we will avoid the for loop and if statement containing: common= array[i] in every iteration. I belive this should make a difference in speed, at least if the array is crazy big.^^

Also, put the return inside the for loops so that you don't iterate the entire list even though you really found that piece of gold :):). (returning something always breaks the entire method.)

Hope I din't missunderstand anything :). Here's some code for you aswell. :)

public static double findUnique(double array[]) {
    double common = 0;

    if(array.length<3){
    throw new IllegalArgumentException("Only two numbers exsists"); 
    }

    // Set up the common number seperately here.
    if(array[0] == array[1]){
      common = array[0];
    }
    else if(array[1] == array[2]){
      return array[0];
    }else{
      return array[1];
    }
    // Now we iterate with return inside the for loop.
    for(int i=2; i<array.length; i++) {
        if(common!=array[i]) {
        return array[i]; 
        }
    }
throw new IllegalArgumentException("All numbers are identical"); 

}

Variable unique is not need at all, possible to use just return array[0], return array[1] and return array[i]; Also after for(...) must be return or throw, or you have compile exception. — Slava Vedenin, Aug 28 '17 at 09:19
You'r right! And you where faster! :) My concept is sound though (hopefully ^^). — Axiomel, Aug 28 '17 at 09:28

score 0 · Answer 3 · answered Aug 28 '17 at 09:14

0

What if you sort the entire array first. Then just look at the first two and one last elements of the array.

answered Aug 28 '17 at 09:14

Gautam

564
2
12

Sure, it would work, but the question is about optimization. Sorting a full array (typically Nlog(N) complexity) for the sole purpose of finding a single outlier (worst case N complexity) is probably not the best solution. – GPI Aug 28 '17 at 09:16
Yes, true. Just that it can go both ways. Wondering what if we find the unique element at the second last position. On second thought, you're right, it'll be an overkill. – Gautam Aug 28 '17 at 09:17
Not sure it can "go both ways". Sorting a list is guaranteed to take **more** than N comparisons. Finding the outlier is guaranteed to take **at most** N(+1 ?) comparisons. – GPI Aug 28 '17 at 09:19
Tried it and the execution time is significantly higher. – Helquin Aug 28 '17 at 09:21

How do I further optimize my code?

3 Answers3