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



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