Program to Convert Decimal Numbers to Binary

#include <iostream>
#include <string>

std::string convertTobinary(long num)
{
std::string binaryVal = "";

if(num == 0) return "0";

while(num != 0)
{
if(num %2 == 0)
binaryVal = "0" + binaryVal;
else
binaryVal = "1" + binaryVal;
num /= 2;
}

return binaryVal;
}

int main(int argc, char **argv)
{
std::cout<<"\n binaryVal : "<<convertTobinary(100);
return 0;
}

Longest Common Sub-Sequence implementation in C++

Problem : Given two sequence of elements (usually characters), find the longest subsequence present in both of them. A subsequence is a sequence that appears in the same order,as appeared in original sequence's  .

Example : Strings  "abc","abd","cde" are sub-sequence of string "abcdefghi".

Solution :  With dynamic programming we can solve this problem in O(m*n) time , where m is length of first sequence and n is length of second sequence.


C++ Solution  :

char *get_lcs(char *first_str,char *sec_str,int str_len1,int str_len2)
{
 int m,n,i,j;
 char temp_lcs[100][100];
 int temp_len_lcs[100][100];
 char ret_str[100];

 memset(temp_lcs,'\0',sizeof(temp_lcs));
 memset(temp_len_lcs,0,sizeof(temp_len_lcs));

 for(m = 0;m<str_len1;m++)
 {
  temp_len_lcs[m][0] = 0;
 }

 for(n = 0;n<str_len2+1;n++)
 {
  temp_len_lcs[0][n] = 0;
 }

 for(m = 0;m<str_len1;m++)
 {
  for(n = 1;n<str_len2+1;n++)
  {
   if(first_str[m] == sec_str[n-1])
   {
    temp_len_lcs[m][n] = temp_len_lcs[m-1][n-2] + 1;
    temp_lcs[m][n-1] = '=';
   }
   else
   {
    if(temp_len_lcs[m-1][n-1] >= temp_len_lcs[m][n-2])
    {
     temp_len_lcs[m][n-1] = temp_len_lcs[m-1][n-1];
     temp_lcs[m][n-1] = '+';
    }
    else
    {
     temp_len_lcs[m][n-1] = temp_len_lcs[m][n-2];
     temp_lcs[m][n-1] = '-';
    }
   }
  }
 }


 memset(ret_str,'\0',sizeof(ret_str));

 i = m;
 j = n;

 while(1)
 {
  if(i == 0 || j == 0)
  {
   break;
  }
  else
  {
   if(temp_lcs[i-1][j-1] == '=')
   {
    i--;
    j--;
    strncat(ret_str,(first_str+i),1);
 
   }
   else if(temp_lcs[i-1][j-1] == '+')
   {
    --i;
   }
   else
   {
    --j;
   }
  }
 }

 return strrev(ret_str);

}


Usage :
Call this function from main  like this

int main(void)
{
 char first_str[100];
 char sec_str[100];
 char lcs[100];

 memset(first_str,'\0',sizeof(first_str));
 memset(sec_str,'\0',sizeof(sec_str));
 memset(lcs,'\0',sizeof(lcs));

 scanf("%s",first_str);
 scanf("%s",sec_str);

 strcpy(lcs,get_lcs(first_str,sec_str,strlen(first_str),strlen(sec_str)));
 std::cout<<lcs<<"\n";

 int a;
 std::cin>>a;
 return 0;
}

Quick sort Implementation in C++

Quick Sort : It is sorting algorithm which takes , O(n*2) time in worst case ,but usually its faster than O(NlogN) algorithms on average case.

It uses , devide and conquer algorithm.
Souce Code : C++ Implementation :

#include <iostream>
#include <cstdio>

using namespace std;

int q_partition(int arr[],int p,int r)
{
    int x,i,j,temp;
   
    x = arr[r];
    i = p-1;
   
    for(j = p;j< (r);j++)
    {
          if(arr[j] <= x)
          {
             i++;
             temp = arr[i];
             arr[i] = arr[j];
             arr[j] = temp;
          }
    }
    temp = arr[i+1];
    arr[i+1] = arr[r];
    arr[r] = temp;
   
    return ++i;
}

void q_sort(int arr[],int p,int r)
{
     if(p < r)
     {
          int q = q_partition(arr,p,r);
          q_sort(arr,p,q-1);
          q_sort(arr,q+1,r);
     }
}

int main(void)
{
    int arr[] = {2,5,1,9,3};
    int i;
   
   
    q_sort(arr,0,4);
    for(i = 0;i<5;i++)
      cout<<"\t"<<arr[i];
   
    int halt;
    cin>>halt;
   
    return 0;
}

Recusive NBit- GrayCode Generator in C++

While Reading tutorials on, one of the , educational institutes website , I have found this interesting property about Gray codes , so i tried implementing it  in C++.

Gray code : The Gray code , is a binary numeral system where two successive values differ in only one bit. It is a non-weighted code.
The reflected binary code was originally designed to prevent spurious output from electromechanical switches. Today, Gray codes are widely used to facilitate error correction in digital communications such as digital terrestrial television and some cable TV systems.
For More Information please refer wiki : http://en.wikipedia.org/wiki/Gray_code

Recursive Algorithm :
1. Write down the Gray code for N – 1 bits.
2. Copy that same list in reverse order below the original one.
3. Add a 0 bit in front of the codings in the original half of the list and a 1 bit in
front of those in the reversed copy.

C++ Code :

/*
* Author :  Nitendra Bhosle
*/
#include <iostream>
#include <vector>
#include <string>

void nBitGrayCodeGenerator(int n,std::vector<std::string>& resultVec)
{
 //Simple Case
 if(n ==1)
 {
  std::string zero = "0";
  std::string one = "1";
  resultVec.push_back(zero);
  resultVec.push_back(one);
 }
 else //Recursively solve problem by deviding it in simpler problems
 {
  std::vector<std::string> temp ;
  nBitGrayCodeGenerator(n-1,temp);

  for(int i = 0;i<temp.size();++i)
  {
   std::string res = "0"+temp[i];
   resultVec.push_back(res);
  }

  for(int i = temp.size()-1;i>=0;--i)
  {
   std::string res = "1"+temp[i];
   resultVec.push_back(res);
  }
 }
}

int main(void)
{
 std::vector<std::string> resultVec;

 nBitGrayCodeGenerator(4,resultVec);

 for(int i=0;i<resultVec.size();++i)
 {
  std::cout<<"\n"<<resultVec[i];
 }

 int halt;
 std::cin>>halt;

 return 0;
}



Result :  5-Bit GrayCode , generated from the above program

00000
00001
00011
00010
00110
00111
00101
00100
01100
01101
01111
01110
01010
01011
01001
01000
11000
11001
11011
11010
11110
11111
11101
11100
10100
10101
10111
10110
10010
10011
10001
10000

Facebook Hacker Cup 2014 – Qualification Round Problem 'Square Detector'

This is easiest problem of this year's hackercup and straightforward to solve  :)

Problem Statement :

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.

Sample Input :

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


Sample Output :

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

Solving problem :
There are few observations to start with
1. If number of black cells in the given input is not perfect square then print "NO".
2. If black cell found at row index i and column index j , and suppose x is square root of number of black cells and size is size of grid then , If (size-i) < x or (size-j) < x print "NO"

Solution in C++ :

/* Author : Nitendra Bhosle
 * Date : 22/11/2013
 */

#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <stdio.h>
#include <cstring>
#include <vector>
#include <cmath>

bool isPerfectSquare(int num)
{
int squareArray[] = { 1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400 };

for(int i = 0;i<20;++i)
{
if(num == squareArray[i])
return true;
}

return false;
}

std::string isSquare(const std::vector<std::string>& inputVec)
{
int numOfBalckCells = 0;
int size = inputVec.size();

for(int i=0;i<size;++i)
{
//std::cout<<"\n"<<inputVec[i];
for(int j=0;j<size;++j)
{
if(inputVec[i][j] == '#')
{
++numOfBalckCells;
}
}
}

//std::cout<<"\n numOfBalckCells "<<numOfBalckCells;
if(!isPerfectSquare(numOfBalckCells))
return "NO";

int squaRoot = (int)std::sqrt((double)numOfBalckCells);
//std::cout<<"\n squaRoot "<<squaRoot;
for(int i=0;i<size;++i)
{
for(int j=0;j<size;++j)
{
if(inputVec[i][j] == '#')
{
//std::cout<<"\n i : "<<i<<"\t j : "<<j<<"\t size : "<<size<<"\t squaRoot : "<<squaRoot;
if(((size-i) < squaRoot) || ((size-j) < squaRoot))
return "NO";

for(int l=0;l<squaRoot;++l)
{
for(int m=0;m<squaRoot;++m)
{
//std::cout<<"\n inputVec[i+l][j+m] : "<<inputVec[i+l][j+m];
if(inputVec[i+l][j+m] != '#')
return "NO";
}
}
//Everything Currect
return "YES";
}
}
}
return "YES";
}

int main(int argc, char **argv)
{
int T,N;
char inpArray[30];
std::vector<std::string> inputVec;

std::cin>>T;
for(int testCase=1;testCase<=T;testCase++)
{
std::cin>>N;
inputVec.clear();
for(int i=0;i<N;++i)
{
memset(inpArray,'/0',sizeof(inpArray));
fscanf(stdin,"%s",inpArray);
inputVec.push_back(inpArray);
}

std::cout<<"Case #"<<testCase<<":"<<isSquare(inputVec)<<std::endl;
}
return 0;
}

INSERTION SORT IN C

Problem :  Given an sequence of N Elements x1,x2,x3 ,........, Generate a permutation of sequence such that : x1<=x2<=x3<=x4 ,...... .

Sol : Start with single element and from second element on wards insert i Th element in proper position in sorted sequence .

Running Time : In Worst Case : O(N^2) , Where N is number of elements in sequence

Source Code  In C :


#include <iostream>

using namespace std;

int main()
{
    char arr[] = {'N','I','T','E','N','D','R','A','B','H','O','S','L','E'};
    int sz = sizeof(arr)/sizeof(char);

    for(int i = 1;i<sz;++i)
    {
        int j = i;
        while(j>=0 && arr[j] < arr[j-1])
        {
            char temp = arr[j-1];
            arr[j-1] = arr[j];
            arr[j] = temp;
            --j;
        }
    }
    for(int i = 0;i<sz;++i)
    {
        cout<<"\n"<<arr[i];
    }
 
   return 0;
}