Reduce the amount of loops when finding if an element is stored only once in the array? [closed]

Question

I was amazed to find that there is a way to reduce the times you loop on an array to find if a element is contained once.

One would think that the only way would be to loop through the whole array, and increasing a variable every time you find a match, and then check if it is equal to 1. However, lets look at this JavaScript code:

function isOnce(itm,arr){
    var first_match=-1;
    for(var i=0,len=arr.length;i<len;i++){
        if(arr[i]===itm){
            first_match=i;
            break;
        }
    }
    if(first_match!=-1){
        var last_match=-1;
        for(i=arr.length-1;i>first_match;i--){
            if(arr[i]===itm){
                last_match=i;
                break;
            }
        }
        if(last_match==-1){
            return true;
        }
    }
    return false;
}

It can reduce the times you loop when these two points met:

• There are 2 or more matches
• The first and last match are at least 1 space apart

so, arr=["a", ...(thousands of items here)... ,"a"]; //we only looped 2 times

I was wondering if there are other ways to reduce the looping in *certain cases.

*There are obviously some cases that one will need to loop through every item on these worst-case scenarios. So it might not work all the time.

Answer 1

D

bool containsOnce(E,R)(R haystack,E needle){
     bool foundOnce=false;
     foreach(e;haystack){
          if(e==needle){
              if(foundOnce)return false;
              foundOnce=true;
          }
     }
     return foundOnce;
}

this is pretty much the best case on unsorted data, you loop until you find a match and then set a flag to true and continue looping, when you find the second match return false immediately, when you looped over the entire thing return state of the flag

this has better timebounds when the double match is found near the beginning of the array (and in general when the items are close together) (but is better in a code-golf contest ;) )

in interest of time bound you'll remain at O(n) regardless on any algorithm (sometimes there simply are no improvements possible except with micro-optimizations). as finding a single match (a subproblem of the current problem) in an unsorted array is O(n)