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!

Last Updated on June 17, 2022 by Ria Pathak

Concepts Used

Sorting

Difficulty Level

Medium

Problem Statement (Simplified):

We have to find a triplet (n_{1}, n_{2}, n_{3}) in array such that sum of two number i.e. n_{1}+n_{2} equals to the third number n_{3}. We have to print the triplet in n_{3} n_{1} n_{2} formation.

See original problem statement here

Test Case

Input:
1
5
20 40 30 50 70

Output:
70 20 50

Explanation:
We can see there are two such triplets (70,20,50) and (50,20,30). As the first triplet has a higher sum value, so we print 70 20 50.

Solving Approach :

Bruteforce Approach:

This problem can be solved if we form three loops for each number and check if the sum of two numbers is equal to the third number, we save all three numbers. Later all loops if no number is present in the array, we print -1. Else we print the largest of them. This approach takes O(n3 ) which is not efficient, so we can solve this more efficiently by given approach.

Efficient Approach :

1) We can find n_{2} if we can subtract n_{1} from n_{3}, so we need to find only the pair n_{3} and n_{1}.
2) We can maintain a hash table which saves the presence of numbers in the array, hash table returns 1 if the number is present in the array, else returns 0.
3) We also know n_{3} will be a larger number in the array, so we can sort the array so that we can iterate all larger numbers serial wise from the last index of the array.
4) So we now iterate from the last index of the sorted array, and find any element from smaller side of the array such that difference of both numbers exists in the array if any such pair exists we print the larger number, smaller number and their difference.

Example

Let array A be,

Sorting array A and maintaining a hash table H which stores value 1 if index x is present in array A, else it stores 0.

Sorted Array A,

Hash Table H,

Required equation is : n_{1}+n_{2}=n_{3}

For n_{3}, we iterate from last index of array MARKDOWN_HASH7fc56270e7a70fa81a5935b72eacbe29MARKDOWNHASH as we need to print the largest value of n{3}, Let the iterator be j=4(last index)

For n_{1}, we ierate from start of array A, Let the iterator be i=0,

  • For i=0, j=4 :
    A[i] = 10, A[j] = 70,
    We check if A[j] - A[i] is present in array or not, which can be verified from hash table H,
    h[A[j] - A[i]]
    h[70 - 10]
    h[60]
    As h[60] is 0, hence, this is not the required triplet, so we check next value of i i.e. i = 1,

  • For i=1, j=4 :
    A[i] = 20, A[j] = 70,
    We check if A[j] - A[i] is present in array or not, which can be verified from hash table H,
    h[A[j] – A[i]]`
    h[70 - 20]
    h[50]
    As h[50] is 1, hence, this is the required triplet, hence, we print the triplet in this form, i.e. A[i] A[j]-A[i] A[j]

Solutions

#include <stdio.h>
void merge(int arr[], int start, int mid, int end){
    int left[mid-start+1];
    int right[end-mid];
    for(int i=start; i<mid+1; i++){
        left[i-start] =  arr[i];
    }
    for(int i=mid+1; i<=end; i++){
        right[i-(mid+1)] = arr[i];
    }
    int leftIndex=0, rightIndex=0, arrIndex=start;
    for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
        if(left[leftIndex]<right[rightIndex]){
            arr[arrIndex] = left[leftIndex++];
        }
        else{
            arr[arrIndex] = right[rightIndex++];
        }
    }

    while(leftIndex<=mid-start){
        arr[arrIndex++] = left[leftIndex++];
    }

    while(rightIndex<end-mid){
        arr[arrIndex++] = right[rightIndex++];
    }

}

void mergeSort(int arr[], int start, int end){
    if(end==start)
        return;
    mergeSort(arr,start,(start+end)/2);
    mergeSort(arr,((start+end)/2)+1,end);
    merge(arr,start,(start+end)/2,end);
}


int main()
{
  int test;
  scanf("%d",&test);

  while(test--){

    int n;
    scanf("%d",&n);

    int arr[n], hash[9999999]={0};
    for(int i=0; i<n; i++){
      scanf("%d",&arr[i]);
      hash[arr[i]] = 1;
    }
    mergeSort(arr,0,n-1);
    int flag = 1;
    for(int i=n-1; i>=0; i--){
      for(int j=0; j<n;j++){
        if( arr[i]-arr[j]>=0 && hash[arr[i]-arr[j]]>0 && arr[i]-arr[j]!=arr[j]){
          printf("%d %d %d\n",arr[i],arr[j], arr[i]-arr[j]);
          flag = 0;
          break;
        }
      }
      if(!flag)
        break;
    }

    if(flag)
      printf("-1\n");

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

void merge(int arr[], int start, int mid, int end){
    int left[mid-start+1]={0};
    int right[end-mid]={0};
    for(int i=start; i<mid+1; i++){
        left[i-start] =  arr[i];
    }
    for(int i=mid+1; i<=end; i++){
        right[i-(mid+1)] = arr[i];
    }
    int leftIndex=0, rightIndex=0, arrIndex=start;
    for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
        if(left[leftIndex]<right[rightIndex]){
            arr[arrIndex] = left[leftIndex++];
        }
        else{
            arr[arrIndex] = right[rightIndex++];
        }
    }

    while(leftIndex<=mid-start){
        arr[arrIndex++] = left[leftIndex++];
    }

    while(rightIndex<end-mid){
        arr[arrIndex++] = right[rightIndex++];
    }

}

void mergeSort(int arr[], int start, int end){
    if(end==start)
        return;
    mergeSort(arr,start,(start+end)/2);
    mergeSort(arr,((start+end)/2)+1,end);
    merge(arr,start,(start+end)/2,end);
}


int main()
{
  int test;
  cin>>test;

  while(test--){

    int n;
    cin>>n;

    int arr[n], hash[9999999]={0};
    for(int i=0; i<n; i++){
      cin>>arr[i];
      hash[arr[i]] = 1;
    }
    mergeSort(arr,0,n-1);
    int flag = 1;
    for(int i=n-1; i>=0; i--){
      for(int j=0; j<n;j++){
        if( arr[i]-arr[j]>=0 && hash[arr[i]-arr[j]]>0 && arr[i]-arr[j]!=arr[j]){
          cout<<arr[i]<<" "<<arr[j]<<" "<<arr[i]-arr[j]<<endl;
          flag = 0;
          break;
        }
      }
      if(!flag)
        break;
    }

    if(flag)
      cout<<-1<<endl;

  }
}
import java.util.*;
import java.io.*;

public class Main {

  static void merge(int arr[], int start, int mid, int end){
      int left[] = new int[mid-start+1];
      int right[] = new int[end-mid];
      for(int i=start; i<mid+1; i++){
          left[i-start] =  arr[i];
      }
      for(int i=mid+1; i<=end; i++){
          right[i-(mid+1)] = arr[i];
      }
      int leftIndex=0, rightIndex=0, arrIndex=start;
      for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
          if(left[leftIndex]<right[rightIndex]){
              arr[arrIndex] = left[leftIndex++];
          }
          else{
              arr[arrIndex] = right[rightIndex++];
          }
      }

      while(leftIndex<=mid-start){
          arr[arrIndex++] = left[leftIndex++];
      }

      while(rightIndex<end-mid){
          arr[arrIndex++] = right[rightIndex++];
      }

  }

  static void mergeSort(int arr[], int start, int end){
      if(end==start)
          return;
      mergeSort(arr,start,(start+end)/2);
      mergeSort(arr,((start+end)/2)+1,end);
      merge(arr,start,(start+end)/2,end);
  }
  public static void main(String args[]) throws IOException {

    Scanner sc = new Scanner(System.in);
    int test = sc.nextInt();

    while(test--!=0){

      int n = sc.nextInt();

      int arr[] = new int[n], hash[] = new int[9999999];
      for(int i=0; i<n; i++){
        arr[i] = sc.nextInt();
        hash[arr[i]] = 1;
      }
      mergeSort(arr,0,n-1);
      int flag = 1;
      for(int i=n-1; i>=0; i--){
        for(int j=0; j<n;j++){
          if(arr[i]-arr[j]>=0 && hash[arr[i]-arr[j]]>0 && arr[i]-arr[j]!=arr[j]){
            System.out.println(arr[i] +  " "  + arr[j] +  " "  + (arr[i]-arr[j]));
            flag = 0;
            break;
          }
        }
        if(flag==0)
          break;
      }

      if(flag==1)
        System.out.println("-1");

    }  

  }
}
def merge(arr, start, mid, end):
	left = [0 for i in range(mid - start + 1)]
	right = [0 for i in range(end - mid)]
	
	for i in range(start, mid + 1):
		left[i - start] =  arr[i]
	
	for i in range(mid + 1, end + 1):
		right[i - (mid + 1)] = arr[i]
	
	leftIndex = 0
	rightIndex = 0
	arrIndex = start
	
	while leftIndex <= mid - start and rightIndex < end - mid:
	
		if(left[leftIndex] < right[rightIndex]):
			arr[arrIndex] = left[leftIndex]
			leftIndex += 1
		
		else:
			arr[arrIndex] = right[rightIndex]
			rightIndex += 1
		
		arrIndex += 1
	
	while(leftIndex <= mid - start):
		arr[arrIndex] = left[leftIndex]
		leftIndex += 1
		arrIndex += 1
	
	while(rightIndex < end - mid):
		arr[arrIndex] = right[rightIndex]
		rightIndex += 1
		arrIndex += 1
	
def mergeSort(arr, start, end):
	if(end == start):
		return
	mergeSort(arr, start, (start + end) // 2)
	mergeSort(arr, ((start + end) // 2) + 1, end)
	merge(arr, start, (start + end) // 2, end)


for _ in range(int(input())):

	n = int(input())
	hash = [0] * 9999999
	arr = list(map(int, input().split()))
	
	for i in arr:
		hash[i] = 1
	
	mergeSort(arr, 0, n - 1)
	flag = 1

	for i in range(n - 1, -1, -1):
		
		for j in range(n):
		
			if arr[i] - arr[j] >= 0 and hash[arr[i] - arr[j]] > 0 and arr[i] - arr[j] != arr[j]:

				print(arr[i], arr[j], arr[i]- arr[j])
				flag = 0
				break

		if not flag:
			break

	if flag:
		print(-1)
# your code goes here

[forminator_quiz id="1386"]

Space Complexity

O( max( array elements) ) to maintain a hash table.

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

Leave a Reply

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