Finding the Subarrays (Hackerearth)


Finding subarrays can become a cumbersome task to handle if we don't know the right approach for it. In this particular question we will be using a new method. 
Pair is used to combine together two values which may be different in type. Pair provides a way to store two heterogeneous objects as a single unit. Such as vector<first attribute, second attribute>.
To access these attributes we use keywords 'first' and 'second'

Approach -
  1. Input values and find total sum of all terms
  2. Create a loop and calculate average term by term, use logic -> 
    1. sum= first element
    2. this_average=sum/elements in the sum
    3. SZ= Elements left in array= size-elements in sum
    4. other_average=(total-sum)/SZ
  3. Use if loop to find whether this_average is bigger than other_average or not.
  4. If true, input the (i+1)th and (j+1)th element in the pair, Increment counter by 1
  5. Sort the pair and output it.

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

int main()
{   
    int n ,count =0;
    cin>>n;
    int arr[n];
    double total;

    for(int i= 0; i<n ;i++)
    {
        cin>>arr[i];
        total+=arr[i];
    }

    vector<pair<int,int>> v; //vector of pairs
    double sum, this_average, other_average;

    for(int i=0;i<n;i++)
    {
        sum=0;
        for(int j=i;j<n;j++)
        {
            sum+=arr[j];
            this_average=sum/(j-i+1);
            int sz= n-j+i-1;
            other_average=(sz>0)?(total-sum)/sz:0;
            if(this_average>other_average)
            {
                v.push_back({i+1,j+1});
                count++;
            }
        }
    }
    cout<<count<<endl;
    sort(v.begin(), v.end());
    for(int i=0;i<v.size(); i++)
    {
        cout<<v[i].first<<" "<<v[i].second<<endl;
    }
    return 0;


    return 0;
}








Popular posts from this blog

Missing Numbers (Hackerrank)

Image
Sometimes the easiest of the questions can become cumbersome and actually put our knowledge to the test. The following question had me writing code for 30 minutes, only to be rejected by the compiler telling me that I was missing something! Question-  Approach -  Make a new array with last element = 0   Input all values of Bigger array Delete similar values found in Smaller array Print all the values which are higher than 0 Now what took me so long? I made nested for loops to check every value of A if it lies in B, if it doesn't, I would append this value to an empty array, sort it and print it. But when i did that, It gave me repeating values and the output was in the form of m+n where m and n are sizes of the array respectively. Hence, I had to do some brainstorming and research which led me to a realization that i can simply add all elements of bigger array brr[m] in a new array C, then delete the same values from C taking elements of arr[n] into consideration!...
Read more

Find Missing Number (Amazon SDE)

Problem - You are given an array from 1 to n, such that all numbers are present except 'x'.  Find 'x' Approach - We know that the sum of all numbers from 1 to n is n(n+1)/2, If we know this value, then we can easily delete the sum of all the elements except x to find x. Code - #include< bits/stdc++.h > using   namespace  std ; int  main () {    int  n ;  cin >> n ;    int  sum_of_n  =   ( n *( n + 1 ))/ 2 ;    int  arr [ n ];    int  sum_of_arr ;    for ( int  i = 0 ; i < n ; i ++)    {     cin >> arr [ i ];     sum_of_arr += arr [ i ];    }    int  x =  sum_of_arr  -  sum_of_n ;   cout << x ;    return   0 ; }
Read more