Check if an element is present in an array using at most floor(N / 2) + 2 comparisons

0 0 6 minutes read

Given an array A[] of size N and an integer X, the task is to check if X exists in A[] with no more than floor(N/2) + 2 comparisons.
Note: For any index i, (i < N) or (A[i] == X) are considered as separate comparisons.

Examples:

Input: A[] = {-3, 5, 11, 3, 100, 2, 88, 22, 7, 900, 23, 4, 1}, X = 88
Output: Yes 8
Explanation: X = 88 exists in the given array, A[] and is detected with 8 comparisons.

Input: A[]= {-3, 5, 11, 3, 100, 2, 88, 22, 7, 900, 23, 4, 1}, X = 6
Output: No
Explanation: X = 6 doesn’t exist in the given array, A[].

Approach: Follow the steps to solve the problem:

Initialize a variable, say T as 1, to store product of all array elements – X i.e (A[i] – X)
Initialize a variable, say comparisons as 0, to store the number of comparisons required.
Initialize pointer, i as 0 to traverse the array.
If the value of N is odd, increment comparisons by 1 because parity of N is checked and update T to T * (A[0] – X) and i to 1.
Therefore, the number of elements in the range [i, N – 1] i.e N – i is always even.
Traverse the array, A[] in range [i, N-1] and perform the following steps:
- Update the value of T to T * (A[i] – X) * (A[i + 1] – X).
- Update i to i + 2 and increment comparisons by 1 because condition i < N is checked.
If the value of T is 0, increment comparisons by 1 because the equality of T is compared. Therefore, X exists in A[] and print “Yes” and number of comparisons.
Otherwise, Print “No” as the result.
The algorithm guarantees that the number of comparisons ? floor(N / 2) + 2.

Below is the implementation of the above approach:

C++

// C++ program for the above approach 
#include <bits/stdc++.h> 
using namespace std; 
  
// Function to check whether X 
// is present in the array A[] 
void findElement(int A[], int N, int X) 
{ 
    // Initialise a pointer 
    int i = 0; 
  
    // Store the number 
    // of comparisons 
    int Comparisons = 0; 
  
    // Variable to store product 
    int T = 1; 
  
    string Found = "No"; 
  
    // Check is N is odd 
    Comparisons++; 
    if (N % 2 == 1) { 
  
        // Update i and T 
        i = 1; 
        T *= (A[0] - X); 
    } 
  
    // Traverse the array 
    for (; i < N; i += 2) { 
  
        // Check if i < N 
        Comparisons += 1; 
  
        // Update T 
        T *= (A[i] - X); 
        T *= (A[i + 1] - X); 
    } 
  
    // Check if T is equal to 0 
    Comparisons += 1; 
    if (T == 0) { 
        cout << "Yes " << Comparisons; 
    } 
    else { 
        cout << "No"; 
    } 
} 
  
// Driver Code 
int main() 
{ 
    // Given Input 
    int A[] = { -3, 5, 11, 3, 100, 2, 88, 
                22, 7, 900, 23, 4, 1 }; 
    int N = sizeof(A) / sizeof(A[0]); 
    int X = 1; 
  
    // Function Call 
    findElement(A, N, X); 
  
    return 0; 
}

Java

// Java program for the above approach 
public class GFG { 
  
    // Function to check whether X 
    // is present in the array A[] 
    static void findElement(int[] A, int N, int X) 
    { 
  
        // Initialise a pointer 
        int i = 0; 
  
        // Store the number 
        // of comparisons 
        int Comparisons = 0; 
  
        // Variable to store product 
        int T = 1; 
  
        // Check is N is odd 
        Comparisons++; 
        if (N % 2 == 1) { 
  
            // Update i and T 
            i = 1; 
            T *= (A[0] - X); 
        } 
  
        // Traverse the array 
        for (; i < N; i += 2) { 
  
            // Check if i < N 
            Comparisons += 1; 
  
            // Update T 
            T *= (A[i] - X); 
            T *= (A[i + 1] - X); 
        } 
  
        // Check if T is equal to 0 
        Comparisons += 1; 
  
        if (T == 0) { 
            System.out.println("Yes " + Comparisons); 
        } 
        else { 
            System.out.println("No"); 
        } 
    } 
  
    // Driver code 
    public static void main(String[] args) 
    {  
      // Given Input 
        // Given Input 
        int[] A = { -3, 5, 11,  3,  100, 2, 88, 
                    22, 7, 900, 23, 4,   1 }; 
        int N = A.length; 
        int X = 1; 
  
        // Function Call 
        findElement(A, N, X); 
    } 
} 
  
// This code is contributed by abhinavjain194

Python3

# Python 3 program for the above approach 
  
# Function to check whether X 
# is present in the array A[] 
def findElement(A, N, X): 
    
    # Initialise a pointer 
    i = 0
  
    # Store the number 
    # of comparisons 
    Comparisons = 0
  
    # Variable to store product 
    T = 1
  
    Found = "No"
  
    # Check is N is odd 
    Comparisons += 1
    if (N % 2 == 1): 
  
        # Update i and T 
        i = 1
        T *= (A[0] - X) 
  
    # Traverse the array 
    while(i< N): 
        
        # Check if i < N 
        Comparisons += 1
  
        # Update T 
        T *= (A[i] - X) 
        T *= (A[i + 1] - X) 
        i += 2
  
    # Check if T is equal to 0 
    Comparisons += 1
    if (T == 0): 
        print("Yes",Comparisons) 
    else: 
        print("No") 
  
# Driver Code 
if __name__ == '__main__': 
    
    # Given Input 
    A = [-3, 5, 11, 3, 100, 2, 88, 22, 7, 900, 23, 4, 1] 
    N = len(A) 
    X = 1
  
    # Function Call 
    findElement(A, N, X) 
      
    # This code is contributed by bgangwar59.

C#

// C# program for the above approach 
using System; 
  
class GFG{ 
      
// Function to check whether X 
// is present in the array A[] 
static void findElement(int[] A, int N, int X) 
{ 
      
    // Initialise a pointer 
    int i = 0; 
  
    // Store the number 
    // of comparisons 
    int Comparisons = 0; 
  
    // Variable to store product 
    int T = 1; 
  
    // Check is N is odd 
    Comparisons++; 
    if (N % 2 == 1) 
    { 
          
        // Update i and T 
        i = 1; 
        T *= (A[0] - X); 
    } 
  
    // Traverse the array 
    for(; i < N; i += 2) 
    { 
          
        // Check if i < N 
        Comparisons += 1; 
  
        // Update T 
        T *= (A[i] - X); 
        T *= (A[i + 1] - X); 
    } 
  
    // Check if T is equal to 0 
    Comparions += 1; 
      
    if (T == 0)  
    { 
        Console.Write("Yes " + Comparisons); 
    } 
    else
    { 
        Console.Write("No"); 
    } 
} 
  
// Driver Code 
public static void Main() 
{ 
      
    // Given Input 
    int[] A = { -3, 5, 11, 3, 100, 2, 88, 
                22, 7, 900, 23, 4, 1 }; 
    int N = A.Length; 
    int X = 1; 
  
    // Function Call 
    findElement(A, N, X); 
} 
} 
  
// This code is contributed by ukasp

Javascript

<script> 
  
// JavaScript program for the above approach 
  
// Function to check whether X 
// is present in the array A[] 
function findElement(A, N, X) 
{ 
    // Initialise a pointer 
    var i = 0; 
  
    // Store the number 
    // of comparisons 
    var Comparisons = 0; 
  
    // Variable to store product 
    var T = 1; 
  
    var Found = "No"; 
  
    // Check is N is odd 
    Comparisons += 1; 
    if (N % 2 == 1) { 
  
        // Update i and T 
        i = 1; 
        T *= (A[0] - X); 
    } 
  
    // Traverse the array 
    for (; i < N; i += 2) { 
  
        // Check if i < N 
        Comparisons += 1; 
  
        // Update T 
        T *= (A[i] - X); 
        T *= (A[i + 1] - X); 
    } 
  
    // Check if T is equal to 0 
    Comparisons += 1; 
    if (T == 0) { 
        document.write("Yes " + Comparisons); 
    } 
    else { 
        document.write("No"); 
    } 
} 
  
// Driver Code 
    // Given Input 
    var A = [-3, 5, 11, 3, 100, 2, 88, 
                22, 7, 900, 23, 4, 1]; 
    var N = A.length; 
    var X = 1; 
  
    // Function Call 
    findElement(A, N, X); 
  
</script>

Output:

Yes 8

Time Complexity: O(N)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!