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!

# Interesting Array

Last Updated on March 28, 2022 by Ria Pathak

### Concepts used:

Two Pointers Technique

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(N2).

#### EFFICIENT METHOD:

1. The idea is to 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;ik)
j--;
else
i++;
}
if(flag==0)

}

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>arr[i];
cin>>k;
int i=0,j=n-1;
int flag =0;
while(ik)
j--;
else
i++;
}
if(flag==0)

}

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;ik)
j--;
else
i++;
}
if(flag==0)
t--;
}
}
}

```
```# your code goes heren, k = map(int,input().split())
arr = list(map(int,input().split()))
i, j = 0, n - 1
flag = 0
while i < j:
if arr[i] + arr[j] == k:
print(i, j)
flag = 1
break
elif arr[i] + arr[j] > k:
j -= 1
else:
i += 1

if flag == 0: