Benchmates

CONCEPTS USED:

Efficient Array Search

DIFFICULTY LEVEL:

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--;
    }

  }
}

[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.