Question

for an array A of size N, and A[0] != A[n-1]. devise an efficient algorithm for find a pair of elements A[i] and A[i+1] such that A[i] != A[i+1]. can you always find such pair and why

Answer 1

/*If you have any query do comment in the comment section else like the solution*/

Since it is given that A[0] != A[n-1], it is always possible to find such pair. Consider below example where an array has n elements. Let's say A[0] = x and A[n-1] = y as A[0] != A[n-1]. Now we can fill elements from 1 to n-2 either with x or y, to make sure that maximum elements in the array are same and we are trying . If we fill the remaining array with x then the required pair can be found at position A[n-2] and A[n-1] and if we fill the remaining array with y then the required pair can be found at position A[0] and A[1]. In case you try to make changes to remaining elements then in that case also you will find a point where two consecutive elements are different.
Eg: n = 5, A[0] = 1, A[4] = 3
Possibilites:

1. Fill remaining array with 1 then

{1, 1, 1, 1, 4}

2. Fill remaining array with 4 then

{1, 4, 4, 4, 4}

In both the above cases we can find a pair where A[i]!=A[i+1] given a condition that A[0] != A[n-1];

Algorithm:

for i = 1 to i = n-1
   if(A[i] != A[i-1]) {
       print("Pair found")
       return true;
   }
return false;