Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Benchmates

Last Updated on June 6, 2022 by Ria Pathak

### CONCEPTS USED:

Efficient Array Search

Medium

### PROBLEM STATEMENT(SIMPLIFIED):

Given marks of `N` students sitting on a bench and a value of `K`, print the index of the student whose marks matches with the value of `K`.

See original problem statement here

#### For Example:

``````Input : N = 10, K = 67
A[] = [60, 61, 62, 63, 63, 64, 65, 66, 67, 66]

Output : 8

Explanation : 67 is present at 8th index (0-based indexing)``````

### SOLVING APPROACH:

#### BRUTEFORCE METHOD

1. Linearly traverse the array, if the value of `K` matches with any element, print its `index value` else print `-1`.

2. `Time Complexity` of this solution is `O(N)`.

### SOLUTIONS:

```#include <stdio.h>

int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,k;
scanf("%d%d",&n,&k);
int arr[n];
int flag=0;
for(int i=0;i<n;i++)
scanf("%d",&arr[i]);
for(int i=0;i<n;i++)
{
if(arr[i]==k)
{
printf("%d\n",i);
flag=1;
break;
}
}
if(flag==0)
printf("-1\n");

}

return 0;
}

```
```#include <bits/stdc++.h>
using namespace std;

int main()
{
int t;cin>>t;
while(t--)
{
int n,k;cin>>n>>k;
int arr[n];
int flag=0;
for(int i=0;i<n;i++)
cin>>arr[i];
for(int i=0;i<n;i++)
{
if(arr[i]==k)
{
cout<<i<<"\n";
flag=1;
break;
}
}
if(flag==0)
cout<<"-1\n";
}
return 0;
}

```

Time Complexity: `O(N)`

Space Complexity: `O(1)`

#### EFFICIENT METHOD:

1. The idea is to use the property that every element is obtained either by adding `1` or `-1` to the previous element. Let the element to be searched is `X`.

2. Check if the value at starting index `(i=0)` matches with `X`, if `Yes` return `i` else there is a possibility of `X` being present at `(i + abs(A[i] - X))` index so increment `i` with `abs(A[i] - X)`.

3. Keep incrementing value of `i`, if `X` is found return `i` else return `-1`.

4. This is an `Efficient Approach` and works better than the `Naive Solution`.

#### ILLUSTRATION:

``````A[] = [60, 61, 62, 63, 63, 64, 65, 66, 67, 66]
K = 67
i = 0

A[0] != K
i = i + abs(A[0] - K) = 0 + (60 - 67) = 7

A[7] != K
i = i + abs(A[7] - X) = 7 + (66 - 67) = 7 + 1 = 8

A[8] = K
Hence we found our K at index = 8.``````

### SOLUTIONS:

```#include <stdio.h>

int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,k;
scanf("%d%d",&n,&k);
int arr[n];
int flag=0;
for(int i=0;i<n;i++)
scanf("%d",&arr[i]);

int i = 0;
while(i<=n-1)
{
if(arr[i]==k)
{
printf("%d\n",i);
break;
}
else
i += abs(arr[i]-k);
}
if(i>n-1)
{
printf("-1\n");
}
}

return 0;
}

```
```#include <bits/stdc++.h>
using namespace std;

int main()
{
int t;cin>>t;
while(t--)
{
int n,k;cin>>n>>k;
int arr[n];
int flag=0;
for(int i=0;i<n;i++)
cin>>arr[i];

int i = 0;
while(i<=n-1)
{
if(arr[i]==k)
{
cout<<i<<"\n";
break;
}
else
i += abs(arr[i]-k);
}
if(i>n-1)
{
cout<<"-1\n";
}
}

return 0;
}

```
```import java.util.*;
import java.io.*;

public class Main {
public static void main(String args[]) throws IOException {

Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t!=0)
{
int n = sc.nextInt();
int k = sc.nextInt();
int arr[] = new int[n];
int flag=0;
for(int i=0;i<n;i++)
arr[i] = sc.nextInt();
for(int i=0;i<n;i++)
{
if(arr[i]==k)
{
System.out.println(i);
flag=1;
break;
}
}
if(flag==0)
System.out.println("-1");
t--;
}

}
}

```

Space Complexity: O(1)

[forminator_quiz id="438"]

This article tried to discuss Efficient Array Search. Hope this blog helps you understand and solve the problem. To practice more problems on Arrays you can check out MYCODE | Competitive Programming.