CODEWITHSUNDEEP
arraysswiftcomparereduce
Chris Marshall
Chris Marshall

Reputation: 5332

Find the missing element in a given permutation

First, a bit of background:

I'm working on one of the Codility lessons, and, even though this is easy to solve, logistically, it is less than easy to solve, performance-wise.

I've been able to boil it down to just this:

public func solution(_ A : inout [Int]) -> Int {
    let B = A   // Assigning it to a local speeds it up.
    return Array<Int>(Set(B)).sorted(by: {$0<$1}).reduce(0) { ($1 == $0 + 1) ? $1 : $0 } + 1
}

However, this is just a WEE bit too slow. I guess that the main reason is that the reduce goes through ALL elements of an array, even though the answer may be early. I may not be able to speed it up.

But I'd like to try. The part that I'm looking at is this:

.reduce(0) { ($1 == $0 + 1) ? $1 : $0 }

I'm wondering if I can make that comparison more efficient.

I have to check if $1 is equal to $0 + 1. I can't avoid that comparison.

The ternary operator is not actually faster than an if clause, but it looks cooler ;).

Is there a higher-performance way to compare two positive integers for equivalence than the basic "==" operator?

BTW: This is not a "do my homework for me" question. It's pretty legit, and these Codility lessons don't give you credit or anything. They are just a fun exercise. I want to know how to do this, as I'm sure I'll need it in the future.

Upvotes: 0

Views: 1929

Answers (3)

Rahul Gautam
Rahul Gautam

Reputation: 86

100 % score in all senses on Codility

  public int solution(int[] A) {

           if(A.length==0) return 1;//empty array needs to return 1(starting number)
           if(A.length==1){
               if(A[0]==1) return 2;//if single element is 1, then 2 is missed
               else return 1; // is single element is not 1, its 1
           } else {
             Arrays.sort(A);
    
            int toreturn = 0;
            for(int i = 0; i<A.length ; i++){
                if(A[i]!= (i+1)){
                    toreturn = i+1;
                    break;
                }
            }
            if(toreturn==0){
            // if toreturn is 0, then missing number is the last one, 
            // so add 1 to the last element since its a permutation**
                toreturn = A[A.length-1]+1;
            }
            return toreturn;
            }
         }

Upvotes: 0

4Rom1
4Rom1

Reputation: 81

100% score in python using an other concept: 

def solution(A):
 Index=0;
 while (Index<len(A)):
  while((A[Index]-1) != Index and A[Index]<=len(A)):
   Tmp=A[Index]; #Permut
   A[Index]=A[Tmp-1];
   A[Tmp-1]=Tmp;
  Index+=1;
 Index=0;
 while Index<len(A):
  if((A[Index]-1) != Index) :
   return Index+1;
  else:
   Index+=1;
 return len(A)+1;  
pass

The idea behind is that for a given permutation, each element A[Index]-1 should match to Index except for the missing element. Elements of the array are then permuted until the correspondence is achieved or not achieved when A[Index]>len(A).

Upvotes: 1

David Pasztor
David Pasztor

Reputation: 54726

Using the solution suggested by @TNguyen in comments, below piece of code got 100% on both correctness and performance.

You just need to generate the correct Array, containing each Integer in the range [1..(N + 1)] by calling Array(1...A.count+1). Then you sum its elements using reduce(0,+) and finally substract the sum of the elements of the input array A. The difference between the two sums gives the missing element.

public func solution(_ A : inout [Int]) -> Int {
    return Array(1...A.count+1).reduce(0,+)-A.reduce(0,+)
}

An even faster solution is to use the mathematical formula1+2+...+n=n(n-1)/2 for the first sum.

public func solution(_ A : inout [Int]) -> Int {
    return (A.count+1)*(A.count+2)/2-A.reduce(0,+)
}

Upvotes: 3

Related Questions