Using Basic Vectors

VECTORS [STL :C++]

Want to sort an array of numbers but failing to choose a perfect sorting algorithm for the same looks cumbersome ? Want to optimize your solutions on sites like Codechef , HackerRank ? 

Then my friend C++ has the answer for you stored in it's STL library. 

STL library contains Vectors Container which is just like an array but with better functionalities. I have commented in the code the syntax and declaration of vector for easy understanding.

Question :

Given the list of numbers, you are to sort them in non decreasing order.

Input

t – the number of numbers in list, then t lines follow [t <= 10^6].

Each line contains one integer: N [0 <= N <= 10^6]

Output

Output given numbers in non decreasing order.

Example

Input:

5
5
3
6
7
1

Output:

1
3
5
6
7

Answer : 

 #include <iostream>  
 #include <vector>  //for vector  
 #include <algorithm> //for sort  
 #include <stdio.h>  
 using namespace std;  
 int main()  
 {  
   long int t,i,temp;  
   vector<long int> v;      //Creating a Vector v  
   scanf("%ld",&t);  
   for(i=0;i<t;i++)  
   {  
     scanf("%ld",&temp);  
     v.push_back(temp);    //adding the element at the end of the vector  
   }  
   sort(v.begin(),v.end());    //the function "sort" is defined in <algorithm.h>  
                    //It takes parameters from the vector as to range which it has to sort  
   for(i=0;i<t;i++)  
   {  
     printf("%ld\n",v[i]);  
   }  
   return 0;  
 }  

IEEE XTREME 7.0

Solution Facebook Hacker Cup 2013

Square Detector

You want to write an image detection system that is able to recognize different geometric shapes. In the first version of the system you settled with just being able to detect filled squares on a grid.

You are given a grid of N×N square cells. Each cell is either white or black. Your task is to detect whether all the black cells form a square shape.

Input

The first line of the input consists of a single number T, the number of test cases.

Each test case starts with a line containing a single integer N. Each of the subsequent N lines contain N characters. Each character is either "." symbolizing a white cell, or "#" symbolizing a black cell. Every test case contains at least one black cell.

Output

For each test case i numbered from 1 to T, output "Case #i: ", followed by YES or NO depending on whether or not all the black cells form a completely filled square with edges parallel to the grid of cells.

Constraints

1 ≤ T ≤ 20

1 ≤ N ≤ 20

Example

Test cases 1 and 5 represent valid squares. Case 2 has an extra cell that is outside of the square. Case 3 shows a square not filled inside. And case 4 is a rectangle but not a square.

Example input

5
4
..##
..##
....
....
4
..##
..##
#...
....
4
####
#..#
#..#
####
5
#####
#####
#####
#####
.....
5
#####
#####
#####
#####
#####

Example output 

Case #1: YES
Case #2: NO
Case #3: NO
Case #4: NO
Case #5: YES



Note: Just omit the last line in your outpfile cause that is extra and your file won't be 
accepted.


SOLUTION :
 #include <iostream>  
 #include <vector>  
 #include <algorithm>  
 #include <fstream>  
 using namespace std;  
 int main()  
 {  
   //ifstream in("in.txt");  
   //ofstream out("out.txt");  
   char a[21][21];  
   int t,num=0,n;  
   cin>>t;  
   //INPUT FROM THE USER  
   while(t--)  
   {  
     num++;  
     int i,j,flag=0,k,x,count=0,final_count=0;  
           vector<int> y;  
     cin>>n;  
     for(i=1;i<=n;i++)  
   {  
     for(j=1;j<=n;j++)  
     {  
       cin>>a[i][j];  
       if (a[i][j]=='#')  
       {  
         final_count++;  
       }  
     }  
   }  
   //STORING FIRST ROW WITH THE OCCURENCE OF "#"  
   for(i=1;i<=n;i++)  
   {  
     for(j=1;j<=n;j++)  
     {  
       if (a[i][j]=='#')  
       {  
           flag=1;  
           x=i;  
           y.push_back(j);  
           //cout<<i<<","<<j<<endl;  
       }  
     }  
     if(flag==1)  
     {  
       break;  
     }  
   }  
   int z=0;  
   for(i=1;i<=n;i++)  
   {  
     for(j=1;j<=n;j++)  
     {  
       if (a[i][j]=='#')  
       {  
         for(k=0;k<y.size();k++)  
         {  
           if(j==y[k])  
           {  
             count++;  
           }  
         }  
       }  
     }  
     if(count==y.size())  
     {  
         //cout<<"row "<<i<<"matched"<<endl;  
         if(x==i)  
         {  
           z++;  
           x++;  
         }  
     }  
     count=0;  
   }  
      //cout<<"z "<<z <<" y.size() "<<y.size()<<endl;  
   cout<<"Case #"<<num;  
   if(final_count!=(z*z))  
   {  
     cout<<": NO"<<endl;  
   }  
   else if(z==y.size())  
   {  
     cout<<": YES"<<endl;  
   }  
   else  
   {  
     cout<<": NO"<<endl;  
   }  
   }  
 return 0;  
 }  




WANT A PROPER EXPLANATION FOR THIS SOLUTION, JUST Comment below . 
#Happy Coding

#CodeScripter

Prime Numbers

PRIME NUMBERS Big Deal,Huh?

Prime Number is a natural number which has exactly two distinct natural number divisors: 1 and itself.

You can most probably figure out the first 10-15 primes by yourself manually. But then,here we are talking about Programming , writing code. So, the first thought that would have come into your mind  would be that of "Brute Force" approach !

Actually , you are right in thinking that checking every number till n [ n is our number till which we have to collect all primes] and dividing it by n-1 numbers to check weather it is divisible or not and so on. Brute Force as it's called.

But frankly speaking the complexity of this code/algorithm would be quite high and you don't want to that unless you don't understand the term  Complexity.

So, here comes the Savior The sieve of eratosthenes .

This algorithm is pretty straight forward and doesn't require nuclear science brains or any other brainstorming session for it's implementation.

Pseudo-code ! 

Input: an integer n > 1
 
Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.
 
for i = 2, 3, 4, ..., √n :
  if A[i] is true:
    for j = i2, i2+i, i2+2i, ..., n:
      A[j] := false
  

Now all i such that A[i] is true are prime. 

The above Image very well illustrates the Algorithm. :)

Still have Doubts.?
This video may help I guess.

Hope your  fear of Prime Number has been conquered a little , but Believe me you are in the right direction of winning the battle.

For more such posts please comment or mail me the topics and I am happy to help. Don't orget to subscribe!