Hackerearth's data structures problems solutions( Odd one Out, Help them Out, Hamiltonian and Lagrangian ) :

Problem 1: Odd one Out

Solution: (in c++)

( please guys before moving to the solution try it yourself at least 3-4 times , if you really wanna become a good coder)

#include<bits/stdc++.h>

using namespace std;

int main()

{

    ios::sync_with_stdio(0); //read here to understand

cin.tie(0);

long long i,n,s=0;

cin>>n;

    long long a[n];

for(int i=0;i<n-1;i++)

{

cin>>a[i];

        s+=a[i]; //s will store the sum of array elements

    }

cout<<(n*n)-s; //see note below

}

Using arithmetic progression sum formula it can be proved that:

1 + 3 + 5 + 7 +.......+n  = n*n

Since sum of A.P = (n/2)*(2*a + (n-1)*d)

here  a = 1 , d = 2

Therefore, sum of A.P = n*n

Hence by subtracting the sum of given elements from the original sum of the set of odd numbers will give us the missing odd number.

 

Problem 2: Help them Out

Solution: (in c++)

( please guys before moving to the solution try it yourself at least 3-4 times , if you really wanna become a good coder)

#include<bits/stdc++.h>

using namespace std;

int main()

{

    long long n,i,ct=0; //ct = count

    cin>>n;

    vector<long long>v(n);

    for(i=0;i<n;i++)

    {

        cin>>v[i]; //putting elements in the vector same as array

    }

    sort(v.begin(),v.end()); //sorting the vector elements

    while(v[n-1]!=0) //loop till max value i.e last value of the vector becomes 0

    {

    for(i=0;i<n;i++) //see note below

    {

        if(v[i]%2!=0) // checking if element is odd

        {

            v[i]--; //updating element

            ct++; //increasing count by 1

        }

    }

    for(i=0;i<n;i++)

    {

        v[i]/=2;

    }

    ct++;

    }

    cout<<ct-1;

}

What we have done here is , first we will be subtracting 1 from all the odd elements in the vector and each subtraction will be counted as 1 move and also updating the value of the element. After subtracting 1 from all the odd elements and counting the moves used , we can see that our vector now contains only even elements. As according to the question: "Half operation halfs the value of each element in the array" now to all the even elements will be divided by 2 and it will be counted as 1 move ( that's why the increment statement is outside of the last for loop). We will repeat these steps till the last element or max element of the vector becomes 0.

For example: The input vector elements are  7 , 8 , 9

therefore ,   vector                  moves required

                     6 8 8                            2

                     3 4 4                            1

                     2 4 4                            1

                     1 2 2                            1

                     0 2 2                            1

                     0 1 1                            1

                     0 0 0                            2      i.e a total of 9 moves

Wondering why i used ct-1 in the end ? I challenge you , Use print statements in the program to find out the glitch... and comment below why ct-1 ?

 

 

Problem 3: Hamiltonian and Lagrangian

Solution: (in c++)

( please guys before moving to the solution try it yourself at least 3-4 times , if you really wanna become a good coder)

#include<bits/stdc++.h>

using namespace std;

int main()

{

    long long n,i,j,k;

cin>>n;

    vector<long long>v(n);

    for(i=0;i<n;i++)

    {

        cin>>v[i];

    }

    for(j=0;j<n;j++) // current element

    {

        for(k=j+1;k<n;k++) //all the right side elements to the current element

        {

            if(v[j]<v[k]) //checking all the right side elements

            {

                break;

            }

            else

            {

                if(k==n-1) //if all the right elements are checked i.e k=n-1

                {

                    cout<<v[j]<<" "; //we will print out the element

                }

            }

        }

    }

    cout<<v[n-1]; //always printing the last element as 

//there's nothing on right side of it

 }

This code is simple. There's no need for any explanation.

Guys , if you have any queries related to a question or need more explanation for a question , comment below!