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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
