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(n^{3}) which is not efficient, so we can solve this more efficiently by given approach by referring some online programming courses.

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

S
#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;

  }
}
#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");

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

    }  

  }
}

Space Complexity

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

Previous post ACTIVITY SELECTION PROBLEM
Next post Find the Window

Leave a Reply

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