Interesting Array

CONCEPTS USED:

Two Pointers Technique

DIFFICULTY LEVEL:

Medium

PROBLEM STATEMENT(SIMPLIFIED):

Given an array A with N elements arranged in an ascending order, also given a number K. Check if their exist two indices such that sum of elements at those indices is equal to K. If Yes print those indices accordingly else print no answer.

NOTE: If there are multiple such pair (i, j), print max j value pair and if all j′s are equal print min i value pair.

See original problem statement here

For Example:

Input : 

N = 5 , K = 34
A = [12, 14, 16, 17, 20]

Output : 1 4

Explanation : elements at index 1 and 4 sum up to give 34 i.e. arr[1] + arr[4] = 34

SOLVING APPROACH:

BRUTEFORCE METHOD:

  1. Naive Solution would be to run two nested loops. Outer loop for picking each element one by one and inner loop for picking rest of the elements one by one.

  2. Check for each index if their exists another index such that the values at both the indexes sum up to the required value, these indexes are our required solution.

  3. Time Complexity of naive approach is O(N^2).

EFFICIENT METHOD:

  1. The idea is to learn programming languages online and use Two Pointers Technique, which is really an easy and effective technique typically used for searching pairs in a sorted array.

  2. We take two pointers, one representing the first element and another representing the last element of the array. Then we add the values kept at both the pointers. If the sum is less than required value, we will shift left pointer to the right by 1 or if their sum is greater than the required value we will shift right pointer towards the left by 1, in order to get closer to the required value. We keep on shifting both the pointers till we get the required value or the required value is not present.

  3. Time Complexity of this technique is O(n).

    NOTE: This technique only works for Sorted Arrays.

Why are we moving left and right in the array?

As the given array is already sorted, lets say X is our current sum of first and last element. If we want a value less than X we can decrement our right pointer by 1 now right will point to an element that is less that the previous element. Similarly if we want a value greater than X, we can simply increment our left pointer by 1, now this will point to an element that is greater than the last element.

ILLUSTRATION:

A[] = [12, 14, 16, 17, 20]
K = 30

i = 0
j = 4
A[i] + A[j] = 12 + 20 = 32
Since A[i] + A[j] > K, j--

i = 0 
j = 3
A[i] + A[j] = 12 + 17 = 29
Since A[i] + A[j] < K, i++

i = 1
j = 3 
A[i] + A[j] = 14 + 17 = 31
Since A[i] + A[j] > K, j--

i = 1
j = 2
A[i] + A[j] = 14 + 16 = 30
Since A[i] + A[j] = K
We found out pair and resultant indexes are (1, 2)

SOLUTIONS:

#include <stdio.h>

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

  }

  return 0;
}

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

int main()
{
  int t;cin>>t;
  while(t--)
  {
    int n,k;cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
      cin>>arr[i];
    cin>>k;
    int i=0,j=n-1;
    int flag =0;
  while(i<j)
  {
    if(arr[i]+arr[j]==k)
    {
      cout<<i<<" "<<j<<"\n";
      flag = 1;
      break;
    }
    else if(arr[i]+arr[j]>k)
      j--;
    else 
      i++;
  }
  if(flag==0)
    cout<<"no answer"<<"\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 arr[] = new int[n];
      for(int i=0;i<n;i++)
        arr[i] = sc.nextInt();
      int k = sc.nextInt();
      int i=0,j=n-1;
      int flag =0;
    while(i<j)
    {
      if(arr[i]+arr[j]==k)
      {
        System.out.println(i + " " + j);
        flag = 1;
        break;
      }
      else if(arr[i]+arr[j]>k)
        j--;
      else 
        i++;
    }
    if(flag==0)
      System.out.println("no answer");
    t--;
    }
  }
}




Previous post Greater than Neighbor
Next post Total number of sub-arrays whose sum value is greater than or equal to K

Leave a Reply

Your email address will not be published. Required fields are marked *