Sherlock and Array (Hackerrank)

Sometimes it's better to stop and first formulate a way to solve a problem before jumping right into it. Why? Well because it gives you more time to better understand a problem and secondly, in some cases even a simpler way to solve a problem. 

Remember kids! When solving algorithms, Math is your friend!
I realized that a little late into this question and when i did, it was just a 5 min snippet.

Question- 




















Approach - It's quite simple and straight forward. 

Instead of dividing array into two halves, getting their sums, checking whether the sums are equal and trying to find out if an element which causes sum to be unequal exist or not, here's a better approach.

array - [5,6,8,11] , here we have 5+6=11 in LHS and 11 in RHS with 8 being an extra element.
Imagine LHS and RHS as same, ex - x+y+x= sum. i.e 2x= sum-y.

Here we just need to check if this equality holds, if it does we print YES and add value to x, else we print NO

Code- 


Popular posts from this blog

Finding the Subarrays (Hackerearth)

Image
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 - Input values and find total sum of all terms Create a loop and calculate average term by term, use logic ->  sum= first element this_average=sum/elements in the sum SZ= Elements left in array= size-elements in sum other_average=(total-sum)/SZ Use if loop to find whether this_average is bigger than other_average or not. If true, input the (i+1)th and (j+1)th element in the pair, Increment counter by 1 Sort the pair and output it. Code- #include< bits/stdc++.h > using namespace std ; int main () {       ...
Read more

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