JSHOP - EDITORIAL

editorial
,
1

PROBLEM LINK:

Contest

Setter: debrc

Tester: dustu_947 , mishra_roshan

Editorialist: debrc

DIFFICULTY:

Cakewalk

PREREQUISITES:

Basic observations, Sorting.

PROBLEM:

Given N number of items, where each item’s price is given in an array P where item i has a price of P_i. Find the 3 items which has the lowest price.

EXPLANATION

A simple sort of array P in increasing order will give you the 3 items of the lowest price in first 3 index of the array P. Add the element in the first 3 index and print it.

TIME COMPLEXITY

Time complexity is O(N logN) to sort the array P.

SOLUTIONS:

Setter's Solution
C++ 
#include <bits/stdc++.h>
using namespace std;

int main() {
	int t;
	cin>>t;
	while(t--)
	{
	    int n;
	    cin>>n;
	    int arr[n];
	    for(int i=0;i<n;i++)
	        cin>>arr[i];
	    sort(arr,arr+n);
	    cout<<arr[0]+arr[1]+arr[2]<<endl;
	}
	return 0;
}
Python 
t=int(input())
for _ in range(t):
    n=int(input())
    a=list(map(int, input().split()))
    a.sort()
    print(a[0] + a[1] + a[2])
Tester's Solution 
#include <iostream>
using namespace std;

int partition(int A[],int p,int r)
{
    int x=A[r];
    int i=p-1;
    for(int j=p;j<r;j++)
    {
        if(A[j]<=x)
        {
            i++;
            int temp=A[i];
            A[i]=A[j];
            A[j]=temp;
        }
    }
    int temp=A[i+1];
        A[i+1]=A[r];
        A[r]=temp;
    return i+1;
}

void quicksort(int A[],int p,int r)
{
    if(p<r)
    {
        int q=partition(A,p,r);
        quicksort(A,p,q-1);
        quicksort(A,q+1,r);
    }
}
int main() {
	// your code goes here
	int T;
	std::cin >> T;
	while(T--)
	{
	   int N;
	   cin>>N;
	   int A[N];
	   for(int i=0;i<N;i++)
	        cin>>A[i];
	   if(N==3)
	   {
	       int s=A[0]+A[1]+A[2];
	       cout<<s<<endl;
	   }
	   else
	   {
	       quicksort(A,0,N-1);
	       int s=A[0]+A[1]+A[2];
	       cout <<s<<endl; 
	   }
	}
	return 0;
}

ALTERNATIVE EXPLANATION

You can also use 3 iteration to filter out 3 smallest numbers which can be done in O(N) complexity.

Feel free to Share your approach.
Suggestions are welcomed as always had been.