Syed Ahmed Zaki

It works on negative cycle.

Implemented Code:

Time Complexity:

O([E].[V])

Reference:
http://cyberlingo.blogspot.com/2015/07/bellman-ford-algorithm.html

Leave a comment

Posted in Algo Unsolved, Bellman Ford, Single Source Shortest Path

Tagged not greedy

Dijkstra

Posted on July 10, 2017 | Leave a comment

#include<bits/stdc++.h>
using namespace std;

int main(){
    int cost[10][10],path[10][10],i,j,n,p,v,min,index=1;
    int distance[10],row,column;

    cout<<"Enter no. of nodes: ";
    cin>>n;
    cout<<"Enter cost matrix: \n";
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            cin>>cost[i][j];
        }
    }
    printf("Enter the node you want to visit:");
    cin>>v;
    printf("Enter the path for the selected node:");
    cin>>p;
    cout<<"Enter the path matrix: \n";
    for(i=1;i<=p;i++)
    {
        for(j=1;j<=n;j++)
        {
            cin>>path[i][j];
        }
    }

    for(i=1;i<=p;i++){
        distance[i]=0;
        row=1;
        for(j=1;j<=n;j++)
        {
            if(row!=v)
            {
                column=path[i][j+1];
                distance[i]=distance[i]+cost[row][column];

            }
            row=column;

        }

    }
    min=distance[1];
for(i=1;i<=p;i++)
{
    if(distance[i]<=min)
    {
        min=distance[i];
        index=i;
    }
}
cout<<"The minimum distance is:";
cout<<min;
for(i=1;i<=n;i++){
    if(path[index][i]!=0)
    {
        printf("-->%d",path[index][i]);
    }
}

}

#include<bits/stdc++.h>

using namespace std;

int main(){

int cost[10][10],path[10][10],i,j,n,p,v,min,index=1;

int distance[10],row,column;

cout<<"Enter no. of nodes: ";

cin>>n;

cout<<"Enter cost matrix: \n";

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

{

for(j=1;j<=n;j++)

{

cin>>cost[i][j];

}

printf("Enter the node you want to visit:");

cin>>v;

printf("Enter the path for the selected node:");

cin>>p;

cout<<"Enter the path matrix: \n";

for(i=1;i<=p;i++)

{

for(j=1;j<=n;j++)

{

cin>>path[i][j];

}

for(i=1;i<=p;i++){

distance[i]=0;

row=1;

for(j=1;j<=n;j++)

{

if(row!=v)

{

column=path[i][j+1];

distance[i]=distance[i]+cost[row][column];

}

row=column;

}

min=distance[1];

for(i=1;i<=p;i++)

{

if(distance[i]<=min)

{

min=distance[i];

index=i;

}

cout<<"The minimum distance is:";

cout<<min;

for(i=1;i<=n;i++){

if(path[index][i]!=0)

{

printf("-->%d",path[index][i]);

}

output:

Enter no. of nodes: 5
Enter cost matrix:
0
4
0
8
0
4
0
3
0
0
0
3
0
4
0
8
0
4
0
7
0
0
0
7
0
Enter the node you want to visit:5
Enter the path for the selected node:2
Enter the path matrix: 1
2
3
4
5
1
4
5
0
0
The minimum distance is:15-->1-->4-->5

Enter no. of nodes: 5

Enter cost matrix:

Enter the node you want to visit:5

Enter the path for the selected node:2

Enter the path matrix: 1

The minimum distance is:15-->1-->4-->5

Complexity:
O(E+V^2)

We are using here adjacency matrix list

Leave a comment

Posted in Dijkstra, Graph, Single Source Shortest Path

Topological Sort

Posted on July 10, 2017 | Leave a comment

code:

// A Java program to print topological sorting of a DAG
import java.io.*;
import java.util.*;

// This class represents a directed graph using adjacency
// list representation
class Graph
{
    private int V;   // No. of vertices
    private LinkedList<Integer> adj[]; // Adjacency List

    //Constructor
    Graph(int v)
    {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; ++i)
            adj[i] = new LinkedList();
    }

    // Function to add an edge into the graph
    void addEdge(int v,int w) { adj[v].add(w); }

    // A recursive function used by topologicalSort
    void topologicalSortUtil(int v, boolean visited[],
                             Stack stack)
    {
        // Mark the current node as visited.
        visited[v] = true;
        Integer i;

        // Recur for all the vertices adjacent to this
        // vertex
        Iterator<Integer> it = adj[v].iterator();
        while (it.hasNext())
        {
            i = it.next();
            if (!visited[i])
                topologicalSortUtil(i, visited, stack);
        }

        // Push current vertex to stack which stores result
        stack.push(new Integer(v));
    }

    // The function to do Topological Sort. It uses
    // recursive topologicalSortUtil()
    void topologicalSort()
    {
        Stack stack = new Stack();

        // Mark all the vertices as not visited
        boolean visited[] = new boolean[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;

        // Call the recursive helper function to store
        // Topological Sort starting from all vertices
        // one by one
        for (int i = 0; i < V; i++)
            if (visited[i] == false)
                topologicalSortUtil(i, visited, stack);

        // Print contents of stack
        while (stack.empty()==false)
            System.out.print(stack.pop() + " ");
    }

    // Driver method
    public static void main(String args[])
    {
        // Create a graph given in the above diagram
        Graph g = new Graph(6);
        g.addEdge(5, 2);
        g.addEdge(5, 0);
        g.addEdge(4, 0);
        g.addEdge(4, 1);
        g.addEdge(2, 3);
        g.addEdge(3, 1);

        System.out.println("Following is a Topological " +
                "sort of the given graph");
        g.topologicalSort();
    }
}

// A Java program to print topological sorting of a DAG

import java.io.*;

import java.util.*;

// This class represents a directed graph using adjacency

// list representation

class Graph

{

private int V; // No. of vertices

private LinkedList<Integer> adj[]; // Adjacency List

//Constructor

Graph(int v)

{

V = v;

adj = new LinkedList[v];

for (int i=0; i<v; ++i)

adj[i] = new LinkedList();

}

// Function to add an edge into the graph

void addEdge(int v,int w) { adj[v].add(w); }

// A recursive function used by topologicalSort

void topologicalSortUtil(int v, boolean visited[],

Stack stack)

{

// Mark the current node as visited.

visited[v] = true;

Integer i;

// Recur for all the vertices adjacent to this

// vertex

Iterator<Integer> it = adj[v].iterator();

while (it.hasNext())

{

i = it.next();

if (!visited[i])

topologicalSortUtil(i, visited, stack);

}

// Push current vertex to stack which stores result

stack.push(new Integer(v));

}

// The function to do Topological Sort. It uses

// recursive topologicalSortUtil()

void topologicalSort()

{

Stack stack = new Stack();

// Mark all the vertices as not visited

boolean visited[] = new boolean[V];

for (int i = 0; i < V; i++)

visited[i] = false;

// Call the recursive helper function to store

// Topological Sort starting from all vertices

// one by one

for (int i = 0; i < V; i++)

if (visited[i] == false)

topologicalSortUtil(i, visited, stack);

// Print contents of stack

while (stack.empty()==false)

System.out.print(stack.pop() + " ");

}

// Driver method

public static void main(String args[])

{

// Create a graph given in the above diagram

Graph g = new Graph(6);

g.addEdge(5, 2);

g.addEdge(5, 0);

g.addEdge(4, 0);

g.addEdge(4, 1);

g.addEdge(2, 3);

g.addEdge(3, 1);

System.out.println("Following is a Topological " +

"sort of the given graph");

g.topologicalSort();

}

Output:

Following is a Topological sort of the given graph
5 4 2 3 1 0

1 2	Following is a Topological sort of the given graph 5 4 2 3 1 0

Time Complexity: O(V+E)
Space Complexity: O(V)
V for vertex E for edge

code courtesy:

Topological Sorting

I understood the theory but need to understand the code well later

Leave a comment

Posted in Graph, Topological Sort

Moving from PHP to C# is a right choice ?

Posted on July 9, 2017 | Leave a comment

https://www.quora.com/Should-I-learn-C-or-PHP

Leave a comment

Posted in Debate

HackerEarth: Batman and Tick-tack-toe

Posted on July 8, 2017 | Leave a comment

This is a basic implementaation problem but need to think critically and I used editorial + previous solved code to understand the logic

code:

#include<iostream>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        char s[4][4];
        int i,j;
        bool ans=false;
        for(i=0; i<4; i++)
        {
            for(j=0; j<4; j++)
            {
                cin>>s[i][j];
            }
        }
        //for column match
        for(i=0;i<2;i++)
        {
            for(j=0;j<4;j++)
            {
                if(s[i][j]=='x'&&s[i+1][j]=='x'&&s[i+2][j]=='.')
                    ans=true;
                if(s[i][j]=='x'&&s[i+1][j]=='.'&&s[i+2][j]=='x')
                    ans=true;
                if(s[i][j]=='.'&&s[i+1][j]=='x'&&s[i+2][j]=='x')
                    ans=true;
            }
        }
        //for row match
        for(i=0;i<4;i++)
        {
            for(j=0;j<2;j++)
            {
                if(s[i][j+1]=='x'&&s[i][j]=='x'&&s[i][j+2]=='.')
                    ans=true;
                if(s[i][j+1]=='x'&&s[i][j]=='.'&&s[i][j+2]=='x')
                    ans=true;
                if(s[i][j+1]=='.'&&s[i][j]=='x'&&s[i][j+2]=='x')
                    ans=true;
            }
        }
        //for diagonal match
        for(i=0;i<2;i++){
            for(j=0;j<2;j++){
                if(s[i][j]=='x'&&s[i+1][j+1]=='x'&&s[i+2][j+2]=='.')
                    ans=true;
                if(s[i][j]=='x'&&s[i+1][j+1]=='.'&&s[i+2][j+2]=='x')
                    ans=true;
                if(s[i][j]=='.'&&s[i+1][j+1]=='x'&&s[i+2][j+2]=='x')
                    ans=true;
            }
        }
        //reverse diagonal match
    for(i=0;i<2;i++)
    {
        for(j=2;j<4;j++)
        {
            if(s[i][j]=='x' && s[i+1][j-1]=='x'&&s[i+2][j-2]=='.')
                ans=true;
            if(s[i][j]=='x' && s[i+1][j-1]=='.'&&s[i+2][j-2]=='x')
                ans=true;
            if(s[i][j]=='.'&&s[i+1][j-1]=='x'&&s[i+2][j-2]=='x')
                ans=true;
        }
    }
    if(ans)
       cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
    }
    return 0;
}

#include<iostream>

using namespace std;

int main()

{

int t;

cin>>t;

while(t--)

{

char s[4][4];

int i,j;

bool ans=false;

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

{

for(j=0; j<4; j++)

{

cin>>s[i][j];

}

//for column match

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

{

for(j=0;j<4;j++)

{

if(s[i][j]=='x'&&s[i+1][j]=='x'&&s[i+2][j]=='.')

ans=true;

if(s[i][j]=='x'&&s[i+1][j]=='.'&&s[i+2][j]=='x')

ans=true;

if(s[i][j]=='.'&&s[i+1][j]=='x'&&s[i+2][j]=='x')

ans=true;

}

//for row match

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

{

for(j=0;j<2;j++)

{

if(s[i][j+1]=='x'&&s[i][j]=='x'&&s[i][j+2]=='.')

ans=true;

if(s[i][j+1]=='x'&&s[i][j]=='.'&&s[i][j+2]=='x')

ans=true;

if(s[i][j+1]=='.'&&s[i][j]=='x'&&s[i][j+2]=='x')

ans=true;

}

//for diagonal match

for(i=0;i<2;i++){

for(j=0;j<2;j++){

if(s[i][j]=='x'&&s[i+1][j+1]=='x'&&s[i+2][j+2]=='.')

ans=true;

if(s[i][j]=='x'&&s[i+1][j+1]=='.'&&s[i+2][j+2]=='x')

ans=true;

if(s[i][j]=='.'&&s[i+1][j+1]=='x'&&s[i+2][j+2]=='x')

ans=true;

}

//reverse diagonal match

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

{

for(j=2;j<4;j++)

{

if(s[i][j]=='x' && s[i+1][j-1]=='x'&&s[i+2][j-2]=='.')

ans=true;

if(s[i][j]=='x' && s[i+1][j-1]=='.'&&s[i+2][j-2]=='x')

ans=true;

if(s[i][j]=='.'&&s[i+1][j-1]=='x'&&s[i+2][j-2]=='x')

ans=true;

}

if(ans)

cout<<"YES"<<endl;

else

cout<<"NO"<<endl;

}

return 0;

}

Leave a comment

Posted in HackerEarth

Tagged tic tac toe

Bucket Sort

Posted on July 7, 2017 | Leave a comment

Pseudocode:

bucketSort(arr[], n)
1) Create n empty buckets (Or lists).
2) Do following for every array element arr[i].
.......a) Insert arr[i] into bucket[n*array[i]]
3) Sort individual buckets using insertion sort.
4) Concatenate all sorted buckets.

bucketSort(arr[], n)

1) Create n empty buckets (Or lists).

2) Do following for every array element arr[i].

.......a) Insert arr[i] into bucket[n*array[i]]

3) Sort individual buckets using insertion sort.

4) Concatenate all sorted buckets.

Implemented Code:

#include<bits/stdc++.h>
using namespace std;
void bucketSort(float A[],int n){
    //1. create an n empty buckets
    vector<float> b[n];
    //2. Put array elements in different buckets
    for(int i=0;i<n;i++)
    {
        int bi=n*A[i]; //index in bucket
        b[bi].push_back(A[i]);
    }
    //3. Sort individual buckets
    for(int i=0;i<n;i++)
    {
        sort(b[i].begin(),b[i].end());
    }
    //4. concatenate all bucket into an array
    int index=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<b[i].size();j++)
        {
            A[index++]=b[i][j];
        }
    {

    }
}
int main()
{
    float arr[]={0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.68};
    int n=sizeof(arr)/sizeof(arr[0]);
    bucketSort(arr,n);
    cout<<"Sorted array is\n";
    for(int i=0;i<n;i++)
    {
        cout<<arr[i]<<" ";
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

void bucketSort(float A[],int n){

//1. create an n empty buckets

vector<float> b[n];

//2. Put array elements in different buckets

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

{

int bi=n*A[i]; //index in bucket

b[bi].push_back(A[i]);

}

//3. Sort individual buckets

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

{

sort(b[i].begin(),b[i].end());

}

//4. concatenate all bucket into an array

int index=0;

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

for(int j=0;j<b[i].size();j++)

{

A[index++]=b[i][j];

}

{

}

int main()

{

float arr[]={0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.68};

int n=sizeof(arr)/sizeof(arr[0]);

bucketSort(arr,n);

cout<<"Sorted array is\n";

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

{

cout<<arr[i]<<" ";

}

return 0;

}

output:

Sorted array is
0.12 0.17 0.21 0.23 0.26 0.39 0.68 0.72 0.78 0.94

1 2	Sorted array is 0.12 0.17 0.21 0.23 0.26 0.39 0.68 0.72 0.78 0.94

Tuts:

Reference:
CLRS: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/bucketSort.htm

Bucket Sort

Harumanchi Book implementation:

#include <stdio.h>
#include <stdlib.h>



int max(int a[],int n)
{
    int max=0,i;
    for(i=0; i<n; i++)
    {
        if(a[i]>max)
        {
            max=a[i];
        }
    }

    return max;
}




void bucket_sort(int a[],int n)
{
    int bucket=max(a,n);
    int b[bucket],i,k,j=-1;


    for(i=0; i<=bucket; i++)
        b[i]=0;




    for(i=0; i<n; i++)
    {
        b[a[i]]=b[a[i]]+1;
    }




    for(i=0; i<=bucket; i++)
    {
        for(k=b[i]; k>0; --k)
        {
            a[++j]=i;
        }
    }


}

int main()
{
    int i;


   // scanf("%d",&n);
    int arr[]={78,17,39,26,72,94,21,12,23,68};
    int n=sizeof(arr)/sizeof(arr[0]);


    bucket_sort(arr,n);

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

        printf(" %d",arr[i]);

    return 0;
}

#include <stdio.h>

#include <stdlib.h>

int max(int a[],int n)

{

int max=0,i;

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

{

if(a[i]>max)

{

max=a[i];

}

return max;

}

void bucket_sort(int a[],int n)

{

int bucket=max(a,n);

int b[bucket],i,k,j=-1;

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

b[i]=0;

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

{

b[a[i]]=b[a[i]]+1;

}

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

{

for(k=b[i]; k>0; --k)

{

a[++j]=i;

}

int main()

{

int i;

// scanf("%d",&n);

int arr[]={78,17,39,26,72,94,21,12,23,68};

int n=sizeof(arr)/sizeof(arr[0]);

bucket_sort(arr,n);

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

printf(" %d",arr[i]);

return 0;

}

output:

 12 17 21 23 26 39 68 72 78 94

1	12 17 21 23 26 39 68 72 78 94

Time and Space complexity: O(n)

Leave a comment

Posted in Bucket Sort

Radix Sort

Posted on July 7, 2017 | Leave a comment

best video:

pseudocode:

Radix-Sort(A, d)
//It works same as counting sort for d number of passes.
//Each key in A[1..n] is a d-digit integer.
//(Digits are numbered 1 to d from right to left.)
    for j = 1 to d do
        //A[]-- Initial Array to Sort
        int count[10] = {0};
        //Store the count of "keys" in count[]
        //key- it is number at digit place j
        for i = 0 to n do
         count[key of(A[i]) in pass j]++
 
        for k = 1 to 10 do
         count[k] = count[k] + count[k-1]
 
        //Build the resulting array by checking
        //new position of A[i] from count[k]
        for i = n-1 downto 0 do
         result[ count[key of(A[i])] ] = A[j]
         count[key of(A[i])]--
 
        //Now main array A[] contains sorted numbers
        //according to current digit place
        for i=0 to n do
          A[i] = result[i]
 
    end for(j)
end func

Radix-Sort(A, d)

//It works same as counting sort for d number of passes.

//Each key in A[1..n] is a d-digit integer.

//(Digits are numbered 1 to d from right to left.)

for j = 1 to d do

//A[]-- Initial Array to Sort

int count[10] = {0};

//Store the count of "keys" in count[]

//key- it is number at digit place j

for i = 0 to n do

count[key of(A[i]) in pass j]++

for k = 1 to 10 do

count[k] = count[k] + count[k-1]

//Build the resulting array by checking

//new position of A[i] from count[k]

for i = n-1 downto 0 do

result[ count[key of(A[i])] ] = A[j]

count[key of(A[i])]--

//Now main array A[] contains sorted numbers

//according to current digit place

for i=0 to n do

A[i] = result[i]

end for(j)

end func

implementation: (I need to clear the radix sort part later..took help to implement)

// C implementation of Radix Sort
#include<bits/stdc++.h>

// This  function gives maximum value in array[]
int getMax(int A[], int n)
{
    int i;
    int max = A[0];
    for (i = 1; i < n; i++){
        if (A[i] > max)
            max = A[i];
    }
    return max;
}

// Main Radix Sort sort function
void radixSort(int A[], int n)
{
    int i,digitPlace = 1;
    int result[n]; // resulting array
    // Find the largest number to know number of digits
    int largestNum = getMax(A, n);


    //we run loop until we reach the largest digit place
    while(largestNum/digitPlace >0){

        int count[10] = {0};
         //Store the count of "keys" or digits in count[]
        for (i = 0; i < n; i++)
            count[ (A[i]/digitPlace)%10 ]++;

        // Change count[i] so that count[i] now contains actual
        //  position of this digit in result[]
        //  Working similar to the counting sort algorithm
        for (i = 1; i < 10; i++)
            count[i] += count[i - 1];

        // Build the resulting array
        for (i = n - 1; i >= 0; i--)
        {
            result[count[ (A[i]/digitPlace)%10 ] - 1] = A[i];
            count[ (A[i]/digitPlace)%10 ]--;
        }

        // Now main array A[] contains sorted
        // numbers according to current digit place
        for (i = 0; i < n; i++)
            A[i] = result[i];

            // Move to next digit place
            digitPlace *= 10;
    }
}

// Function to print an array
void printArray(int A[], int n)
{
    int i;
    for (i = 0; i < n; i++)
    printf("%d ", A[i]);
    printf("\n");
}

// Driver program to test above functions
int main()
{
    int a[] = {432,312,304,310,123,124};
    int n = sizeof(a)/sizeof(a[0]);
    printf("Unsorted Array: ");
    printArray(a, n);

    radixSort(a, n);

    printf("Sorted Array: ");
    printArray(a, n);
    return 0;
}

// C implementation of Radix Sort

#include<bits/stdc++.h>

// This function gives maximum value in array[]

int getMax(int A[], int n)

{

int i;

int max = A[0];

for (i = 1; i < n; i++){

if (A[i] > max)

max = A[i];

}

return max;

}

// Main Radix Sort sort function

void radixSort(int A[], int n)

{

int i,digitPlace = 1;

int result[n]; // resulting array

// Find the largest number to know number of digits

int largestNum = getMax(A, n);

//we run loop until we reach the largest digit place

while(largestNum/digitPlace >0){

int count[10] = {0};

//Store the count of "keys" or digits in count[]

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

count[ (A[i]/digitPlace)%10 ]++;

// Change count[i] so that count[i] now contains actual

// position of this digit in result[]

// Working similar to the counting sort algorithm

for (i = 1; i < 10; i++)

count[i] += count[i - 1];

// Build the resulting array

for (i = n - 1; i >= 0; i--)

{

result[count[ (A[i]/digitPlace)%10 ] - 1] = A[i];

count[ (A[i]/digitPlace)%10 ]--;

}

// Now main array A[] contains sorted

// numbers according to current digit place

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

A[i] = result[i];

// Move to next digit place

digitPlace *= 10;

}

// Function to print an array

void printArray(int A[], int n)

{

int i;

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

printf("%d ", A[i]);

printf("\n");

}

// Driver program to test above functions

int main()

{

int a[] = {432,312,304,310,123,124};

int n = sizeof(a)/sizeof(a[0]);

printf("Unsorted Array: ");

printArray(a, n);

radixSort(a, n);

printf("Sorted Array: ");

printArray(a, n);

return 0;

}

Reference:

Radix Sort – Explanation, Pseudocode and Implementation

Time complexity: O(d*n)==O(n)
Where d is the digit of the number

Leave a comment

Posted in Pore Abar Bujhbo, Radix Sort

Counting Sort

Posted on July 7, 2017 | Leave a comment

Algo:

COUNTING-SORT(A,B,k)
 
1. let C[0..k] be a new array
 
2. for i = 0 to k
 
3. 		C[i] = 0
 
4. for j = 1 to A.length
 
5. 		C[A[j]] = C[A[j]] + 1
 
6. // C[i] now contains the number of elements equal to i .
 
7. for i = 1 to k
 
8. 		C[i] = C[i] + C[i - 1]
 
9. // C[i] now contains the number of elements less than or equal to i .
 
10.for j = A.length downto 1
 
11.		B[C[A[j]]] = A[j]
 
12.		C[A[j]] = C[A[j]] - 1

COUNTING-SORT(A,B,k)

1. let C[0..k] be a new array

2. for i = 0 to k

3. C[i] = 0

4. for j = 1 to A.length

5. C[A[j]] = C[A[j]] + 1

6. // C[i] now contains the number of elements equal to i .

7. for i = 1 to k

8. C[i] = C[i] + C[i - 1]

9. // C[i] now contains the number of elements less than or equal to i .

10.for j = A.length downto 1

11. B[C[A[j]]] = A[j]

12. C[A[j]] = C[A[j]] - 1

Implemented Code:

#include<bits/stdc++.h>
using namespace std;
void countingSort(int a[],int k,int n)
{
    int i,j;
    int b[15],c[100];
    for(i=0;i<=k;i++)
        c[i]=0;
    for(j=1;j<=n;j++)
        c[a[j]]=c[a[j]]+1;
    for(i=1;i<=k;i++)
        c[i]=c[i]+c[i-1];
    for(j=n;j>=1;j--)
    {
        b[c[a[j]]]=a[j];
        c[a[j]]=c[a[j]]-1;
    }
    cout<<"Sorted Array is:"<<endl;
    for(i=1;i<=n;i++)
    {
        cout<<" ";
        cout<<b[i];
    }
}
int main()
{

    int i,k=9; //k means maximum value in an array
  
    int A[]={5,2,9,5,2,3,5};
    int n=sizeof(A)/sizeof(A[0]);
    countingSort(A,k,n);

return 0;
}

#include<bits/stdc++.h>

using namespace std;

void countingSort(int a[],int k,int n)

{

int i,j;

int b[15],c[100];

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

c[i]=0;

for(j=1;j<=n;j++)

c[a[j]]=c[a[j]]+1;

for(i=1;i<=k;i++)

c[i]=c[i]+c[i-1];

for(j=n;j>=1;j--)

{

b[c[a[j]]]=a[j];

c[a[j]]=c[a[j]]-1;

}

cout<<"Sorted Array is:"<<endl;

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

{

cout<<" ";

cout<<b[i];

}

int main()

{

int i,k=9; //k means maximum value in an array

int A[]={5,2,9,5,2,3,5};

int n=sizeof(A)/sizeof(A[0]);

countingSort(A,k,n);

return 0;

}

Reference:
http://scanftree.com/Data_Structure/Counting-sort

Counting Sort in C

CLRS:
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/countingSort.htm

Tuts:

Complexity:
Time: O(k)+O(n)+O(k)+O(n)=O(n) if K=O(n)
Space: O(n)

Leave a comment

Posted in Counting Sort, Quicksort, Sorting

Binary Search Tree: Successor in Inorder Traversal

Posted on July 6, 2017 | Leave a comment

code:

/* C++ program to find Inorder successor in a BST */
#include<bits/stdc++.h>
using namespace std;
struct Node {
	int data;
	struct Node *left;
	struct Node *right;
};

//Function to find some data in the tree
Node* Find(Node*root, int data) {
	if(root == NULL) return NULL;
	else if(root->data == data) return root;
	else if(root->data < data) return Find(root->right,data);
	else return Find(root->left,data);
}

//Function to find Node with minimum value in a BST
struct Node* FindMin(struct Node* root) {
	if(root == NULL) return NULL;
	while(root->left != NULL)
		root = root->left;
	return root;
}

//Function to find Inorder Successor in a BST
struct Node* Getsuccessor(struct Node* root,int data) {
	// Search the Node - O(h)
	struct Node* current = Find(root,data);
	if(current == NULL) return NULL;
	if(current->right != NULL) {  //Case 1: Node has right subtree
		return FindMin(current->right); // O(h)
	}
	else {   //Case 2: No right subtree  - O(h)
		struct Node* successor = NULL;
		struct Node* ancestor = root;
		while(ancestor != current) {
			if(current->data < ancestor->data) {
				successor = ancestor; // so far this is the deepest node for which current node is in left
				ancestor = ancestor->left;
			}
			else
				ancestor = ancestor->right;
		}
		return successor;
	}
}

//Function to visit nodes in Inorder
void Inorder(Node *root) {
	if(root == NULL) return;

	Inorder(root->left);       //Visit left subtree
	printf("%d ",root->data);  //Print data
	Inorder(root->right);      // Visit right subtree
}

// Function to Insert Node in a Binary Search Tree
Node* Insert(Node *root,char data) {
	if(root == NULL) {
		root = new Node();
		root->data = data;
		root->left = root->right = NULL;
	}
	else if(data <= root->data)
		root->left = Insert(root->left,data);
	else
		root->right = Insert(root->right,data);
	return root;
}

int main() {
	/*Code To Test the logic
	  Creating an example tree
	                    5
			   / \
			  3   10
			 / \   \
			1   4   11
    */
	Node* root = NULL;
	root = Insert(root,5); 
        root = Insert(root,10);
	root = Insert(root,3); 
        root = Insert(root,4);
	root = Insert(root,1); 
        root = Insert(root,11);

	//Print Nodes in Inorder
	cout<<"Inorder Traversal: ";
	Inorder(root);
	cout<<"\n";

	// Find Inorder successor of some node.
	struct Node* successor = Getsuccessor(root,1);
	if(successor == NULL) cout<<"No successor Found\n";
	else
    cout<<"Successor is "<<successor->data<<"\n";
}

/* C++ program to find Inorder successor in a BST */

#include<bits/stdc++.h>

using namespace std;

struct Node {

int data;

struct Node *left;

struct Node *right;

};

//Function to find some data in the tree

Node* Find(Node*root, int data) {

if(root == NULL) return NULL;

else if(root->data == data) return root;

else if(root->data < data) return Find(root->right,data);

else return Find(root->left,data);

}

//Function to find Node with minimum value in a BST

struct Node* FindMin(struct Node* root) {

if(root == NULL) return NULL;

while(root->left != NULL)

root = root->left;

return root;

}

//Function to find Inorder Successor in a BST

struct Node* Getsuccessor(struct Node* root,int data) {

// Search the Node - O(h)

struct Node* current = Find(root,data);

if(current == NULL) return NULL;

if(current->right != NULL) { //Case 1: Node has right subtree

return FindMin(current->right); // O(h)

}

else { //Case 2: No right subtree - O(h)

struct Node* successor = NULL;

struct Node* ancestor = root;

while(ancestor != current) {

if(current->data < ancestor->data) {

successor = ancestor; // so far this is the deepest node for which current node is in left

ancestor = ancestor->left;

}

else

ancestor = ancestor->right;

}

return successor;

}

//Function to visit nodes in Inorder

void Inorder(Node *root) {

if(root == NULL) return;

Inorder(root->left); //Visit left subtree

printf("%d ",root->data); //Print data

Inorder(root->right); // Visit right subtree

}

// Function to Insert Node in a Binary Search Tree

Node* Insert(Node *root,char data) {

if(root == NULL) {

root = new Node();

root->data = data;

root->left = root->right = NULL;

}

else if(data <= root->data)

root->left = Insert(root->left,data);

else

root->right = Insert(root->right,data);

return root;

}

int main() {

/*Code To Test the logic

Creating an example tree

/ \

3 10

/ \ \

1 4 11

Node* root = NULL;

root = Insert(root,5);

root = Insert(root,10);

root = Insert(root,3);

root = Insert(root,4);

root = Insert(root,1);

root = Insert(root,11);

//Print Nodes in Inorder

cout<<"Inorder Traversal: ";

Inorder(root);

cout<<"\n";

// Find Inorder successor of some node.

struct Node* successor = Getsuccessor(root,1);

if(successor == NULL) cout<<"No successor Found\n";

else

cout<<"Successor is "<<successor->data<<"\n";

}

Leave a comment

Posted in Binary Search Tree, Tree

Delete a node in Binary Search Tree

Posted on July 5, 2017 | Leave a comment

code:

#include<bits/stdc++.h>
using namespace std;

struct Node{
    int data;
    struct Node* left;
    struct Node* right;
};

Node* FindMin(Node* root)
{
    while(root->left!=NULL)
        root=root->left;
    return root;
}

//Function to search a delete value from tree
struct Node* Delete(struct Node *root, int data)
{

    if(root==NULL)
        return root;
    else if(data<root->data)
        root->left=Delete(root->left,data);
    else if(data>root->data)
        root->right=Delete(root->right,data);
    else{
        //case 1: No child
        if(root->left==NULL && root->right==NULL)
        {
            delete root;
            root=NULL;
        }
        //case 2: one child
        else if(root->left==NULL)
        {
            struct Node* temp=root;
            root=root->right;
            delete temp;
        }
        else if(root->right==NULL)
        {
            struct Node* temp=root;
            root=root->left;
            delete temp;
        }
        //case 3: 2 children
        else{
            struct Node * temp=FindMin(root->right);
            root->data=temp->data;
            root->right=Delete(root->right, temp->data);
        }

    }
return root;
}

//function to visit nodes in inorder
void Inorder(Node* root)
{
    if(root==NULL)
          return;
    Inorder(root->left); //visit left subtree
    printf("%d ",root->data); //print data
    Inorder(root->right); //visit right subtree
}


Node* Insert(Node *root, char data)
{
    if(root==NULL)
    {
        root=new Node();
        root->data=data;
        root->left=root->right=NULL;
    }
    else if(data<=root->data)
        root->left=Insert(root->left,data);
    else
        root->right=Insert(root->right,data);
    return root;
}

int main()
{
    Node *root=NULL;
    root=Insert(root,5);
    root=Insert(root,10);
    root=Insert(root,3);
    root=Insert(root,4);
    root=Insert(root,1);
    root=Insert(root,11);

    root=Delete(root,5);

    //Print Nodes in Inorder
    cout<<"Inorder: ";
    Inorder(root);
    cout<<"\n";

}

100

101

#include<bits/stdc++.h>

using namespace std;

struct Node{

int data;

struct Node* left;

struct Node* right;

};

Node* FindMin(Node* root)

{

while(root->left!=NULL)

root=root->left;

return root;

}

//Function to search a delete value from tree

struct Node* Delete(struct Node *root, int data)

{

if(root==NULL)

return root;

else if(data<root->data)

root->left=Delete(root->left,data);

else if(data>root->data)

root->right=Delete(root->right,data);

else{

//case 1: No child

if(root->left==NULL && root->right==NULL)

{

delete root;

root=NULL;

}

//case 2: one child

else if(root->left==NULL)

{

struct Node* temp=root;

root=root->right;

delete temp;

}

else if(root->right==NULL)

{

struct Node* temp=root;

root=root->left;

delete temp;

}

//case 3: 2 children

else{

struct Node * temp=FindMin(root->right);

root->data=temp->data;

root->right=Delete(root->right, temp->data);

}

return root;

}

//function to visit nodes in inorder

void Inorder(Node* root)

{

if(root==NULL)

return;

Inorder(root->left); //visit left subtree

printf("%d ",root->data); //print data

Inorder(root->right); //visit right subtree

}

Node* Insert(Node *root, char data)

{

if(root==NULL)

{

root=new Node();

root->data=data;

root->left=root->right=NULL;

}

else if(data<=root->data)

root->left=Insert(root->left,data);

else

root->right=Insert(root->right,data);

return root;

}

int main()

{

Node *root=NULL;

root=Insert(root,5);

root=Insert(root,10);

root=Insert(root,3);

root=Insert(root,4);

root=Insert(root,1);

root=Insert(root,11);

root=Delete(root,5);

//Print Nodes in Inorder

cout<<"Inorder: ";

Inorder(root);

cout<<"\n";

}

Leave a comment

Posted in Binary Search Tree, Tree

Interview Question: Stack vs Heap

Posted on July 5, 2017 | Leave a comment

best:

Leave a comment

Posted in Interview

Traversal in Binary Search Tree

Posted on July 4, 2017 | Leave a comment

Height of a binary tree:

Level Order BFS in Binary Search Tree:

#include<bits/stdc++.h>
#include<queue>
using namespace std;

struct Node
{
    char data;
    Node *left;
    Node *right;
};
//Function to print nodes in a binary tree in level order
void LevelOrder(Node *root)
{
    if(root==NULL)
        return;
    queue<Node*> Q;
    Q.push(root);
    //while there is at least one discovered node
    while(!Q.empty())
    {
        Node* current=Q.front();
        Q.pop();
        cout<<current->data<<" ";
        if(current->left!=NULL)
            Q.push(current->left);
        if(current->right!=NULL)
            Q.push(current->right);
    }
}
//Function to insert node in a binary search tree
Node* Insert(Node *root, char data)
{
    if(root==NULL)
    {
        root=new Node();
        root->data=data;
        root->left=root->right=NULL;
    }
    else if(data<=root->data)
        root->left=Insert(root->left,data);
    else
        root->right=Insert(root->right,data);
    return root;
}
int main()
{

    //creating an example tree

    Node *root=NULL;
    root=Insert(root,'M');
    root=Insert(root,'B');
    root=Insert(root,'Q');
    root=Insert(root,'Z');
    root=Insert(root,'A');
    root=Insert(root,'C');
    LevelOrder(root);
}

#include<bits/stdc++.h>

#include<queue>

using namespace std;

struct Node

{

char data;

Node *left;

Node *right;

};

//Function to print nodes in a binary tree in level order

void LevelOrder(Node *root)

{

if(root==NULL)

return;

queue<Node*> Q;

Q.push(root);

//while there is at least one discovered node

while(!Q.empty())

{

Node* current=Q.front();

Q.pop();

cout<<current->data<<" ";

if(current->left!=NULL)

Q.push(current->left);

if(current->right!=NULL)

Q.push(current->right);

}

//Function to insert node in a binary search tree

Node* Insert(Node *root, char data)

{

if(root==NULL)

{

root=new Node();

root->data=data;

root->left=root->right=NULL;

}

else if(data<=root->data)

root->left=Insert(root->left,data);

else

root->right=Insert(root->right,data);

return root;

}

int main()

{

//creating an example tree

Node *root=NULL;

root=Insert(root,'M');

root=Insert(root,'B');

root=Insert(root,'Q');

root=Insert(root,'Z');

root=Insert(root,'A');

root=Insert(root,'C');

LevelOrder(root);

}

output:

M B Q A C Z

1	M B Q A C Z

DFS in Preorder, Inorder, Postorder:

#include<bits/stdc++.h>
#include<queue>
using namespace std;

struct Node
{
    char data;
    Node *left;
    Node *right;
};
//Function to print nodes in a binary tree in level order
void Preorder(struct Node* root){

    if(root==NULL)
        return;
    printf("%c ",root->data);//print data
    Preorder(root->left); //visit left subtree
    Preorder(root->right); //Visit right subtree
}

//function to visit nodes in Inorder
void Inorder(Node* root)
{
    if(root==NULL)
        return;
    Inorder(root->left); //Visit left subtree
    printf("%c ",root->data); //Print  data
    Inorder(root->right); //Visit right subtree
}

void Postorder(Node* root)
{
    if(root==NULL)
        return;
    Postorder(root->left); //visit left subtree
    Postorder(root->right); //visit right subtree
    printf("%c ",root->data); //print data


}


//Function to insert node in a binary search tree
Node* Insert(Node *root, char data)
{
    if(root==NULL)
    {
        root=new Node();
        root->data=data;
        root->left=root->right=NULL;
    }
    else if(data<=root->data)
        root->left=Insert(root->left,data);
    else
        root->right=Insert(root->right,data);
    return root;
}
int main()
{

    //creating an example tree

    Node *root=NULL;
    root=Insert(root,'M');
    root=Insert(root,'B');
    root=Insert(root,'Q');
    root=Insert(root,'Z');
    root=Insert(root,'A');
    root=Insert(root,'C');

    //Print nodes in preorder
    cout<<"Preorder: ";
    Preorder(root);
    cout<<endl;
    //Print nodes in in inorder
    cout<<"Inorder:  ";
    Inorder(root);
    cout<<endl;
    //Print Nodes in postorder
    cout<<"Postorder: ";
    Postorder(root);
    cout<<endl;
    return 0;
}

#include<bits/stdc++.h>

#include<queue>

using namespace std;

struct Node

{

char data;

Node *left;

Node *right;

};

//Function to print nodes in a binary tree in level order

void Preorder(struct Node* root){

if(root==NULL)

return;

printf("%c ",root->data);//print data

Preorder(root->left); //visit left subtree

Preorder(root->right); //Visit right subtree

}

//function to visit nodes in Inorder

void Inorder(Node* root)

{

if(root==NULL)

return;

Inorder(root->left); //Visit left subtree

printf("%c ",root->data); //Print data

Inorder(root->right); //Visit right subtree

}

void Postorder(Node* root)

{

if(root==NULL)

return;

Postorder(root->left); //visit left subtree

Postorder(root->right); //visit right subtree

printf("%c ",root->data); //print data

}

//Function to insert node in a binary search tree

Node* Insert(Node *root, char data)

{

if(root==NULL)

{

root=new Node();

root->data=data;

root->left=root->right=NULL;

}

else if(data<=root->data)

root->left=Insert(root->left,data);

else

root->right=Insert(root->right,data);

return root;

}

int main()

{

//creating an example tree

Node *root=NULL;

root=Insert(root,'M');

root=Insert(root,'B');

root=Insert(root,'Q');

root=Insert(root,'Z');

root=Insert(root,'A');

root=Insert(root,'C');

//Print nodes in preorder

cout<<"Preorder: ";

Preorder(root);

cout<<endl;

//Print nodes in in inorder

cout<<"Inorder: ";

Inorder(root);

cout<<endl;

//Print Nodes in postorder

cout<<"Postorder: ";

Postorder(root);

cout<<endl;

return 0;

}

output:

Preorder: M B A C Q Z
Inorder:  A B C M Q Z
Postorder: A C B Z Q M

Preorder: M B A C Q Z

Inorder: A B C M Q Z

Postorder: A C B Z Q M

Leave a comment

Posted in Binary Search Tree, Tree

Binary Search Tree

Posted on July 4, 2017 | Leave a comment

youtube :

code:

#include<iostream>
using namespace std;
//Definition of Node for Binary search tree
struct BstNode
{
    int data;
    BstNode* left;
    BstNode* right;
};
//Function to create new Node in heap
BstNode* GetNewNode(int data)
{
    BstNode* newNode=new BstNode();
    newNode->data=data;
    newNode->left=newNode->right=NULL;
    return newNode;
}
//To search an element in BST return true if element is found
bool Search(BstNode* root, int data)
{
    if(root==NULL)
        return false;
    else if(root->data==data)
        return true;
    else if(data<=root->data)
        return Search(root->left,data);
    else
        return Search(root->right,data);
}
//TO insert data in BST, return address of root node
BstNode* Insert(BstNode* root, int data)
{
    if(root==NULL) //empty tree
    {
        root=GetNewNode(data);
    }
    //if data to be inserted is lesser, insert it in left subtree
    else if(data<=root->data)
    {
        root->left=Insert(root->left,data);
    }
    //else, insert in right subtree
    else
    {
        root->right=Insert(root->right,data);
    }
    return root;
}

int main()
{
    BstNode* root=NULL;//creating an empty tree
    /* Code to test the logic */
    root=Insert(root,15);
    root=Insert(root,10);
    root=Insert(root,20);
    root=Insert(root,25);
    root=Insert(root,8);
    root=Insert(root,12);
    //asking user to enter a number
    int number;
    cout<<"Enter number to be searched:\n";
    cin>>number;
    //If number is found, print "FOUND"
    if(Search(root,number)==true)
        cout<<"Found\n";
    else
        cout<<"Not Found\n";
    return 0;
}

#include<iostream>

using namespace std;

//Definition of Node for Binary search tree

struct BstNode

{

int data;

BstNode* left;

BstNode* right;

};

//Function to create new Node in heap

BstNode* GetNewNode(int data)

{

BstNode* newNode=new BstNode();

newNode->data=data;

newNode->left=newNode->right=NULL;

return newNode;

}

//To search an element in BST return true if element is found

bool Search(BstNode* root, int data)

{

if(root==NULL)

return false;

else if(root->data==data)

return true;

else if(data<=root->data)

return Search(root->left,data);

else

return Search(root->right,data);

}

//TO insert data in BST, return address of root node

BstNode* Insert(BstNode* root, int data)

{

if(root==NULL) //empty tree

{

root=GetNewNode(data);

}

//if data to be inserted is lesser, insert it in left subtree

else if(data<=root->data)

{

root->left=Insert(root->left,data);

}

//else, insert in right subtree

else

{

root->right=Insert(root->right,data);

}

return root;

}

int main()

{

BstNode* root=NULL;//creating an empty tree

/* Code to test the logic */

root=Insert(root,15);

root=Insert(root,10);

root=Insert(root,20);

root=Insert(root,25);

root=Insert(root,8);

root=Insert(root,12);

//asking user to enter a number

int number;

cout<<"Enter number to be searched:\n";

cin>>number;

//If number is found, print "FOUND"

if(Search(root,number)==true)

cout<<"Found\n";

else

cout<<"Not Found\n";

return 0;

}

Leave a comment

Posted in Binary Search Tree, Tree

Hackerearth: COUNT NUMBERS

Posted on July 2, 2017 | Leave a comment

code:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t,n,i,a;
    string s;
    cin>>t;

    while(t--)
    {
        int c=0;
        cin>>n;
        cin>>s;
        for(i=0; i<=n; i++)
        {
            if(s[i]>=48 && s[i]<=57)
            {
                a++;  //this is increasing when a digit is found
            }
            else
            {
                if(a!=0)
                {
                    c++; //must check this logic
                }
                a=0;    //must check this logic
            }

        }
        cout<<c<<endl; //printing how many numbers are here
    }



    return 0;
}

#include<bits/stdc++.h>

using namespace std;

int main()

{

int t,n,i,a;

string s;

cin>>t;

while(t--)

{

int c=0;

cin>>n;

cin>>s;

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

{

if(s[i]>=48 && s[i]<=57)

{

a++; //this is increasing when a digit is found

}

else

{

if(a!=0)

{

c++; //must check this logic

}

a=0; //must check this logic

}

cout<<c<<endl; //printing how many numbers are here

}

return 0;

}

Leave a comment

Posted in Adhoc/Brute Force, HackerEarth, Logic Logic

Syed Ahmed Zaki

Floyd Warshall Algorithm

Bellman Ford

Dijkstra

Topological Sort

Moving from PHP to C# is a right choice ?

HackerEarth: Batman and Tick-tack-toe

Bucket Sort

Radix Sort

Counting Sort

Binary Search Tree: Successor in Inorder Traversal

Delete a node in Binary Search Tree

Interview Question: Stack vs Heap

Traversal in Binary Search Tree

Binary Search Tree

Hackerearth: COUNT NUMBERS

Caution and Tips:

Category

About Me & MyBlog

Recent Posts

Recent Comments

My Facebook

My Algorithmic Progress in OJ’s

My Github

My Linkedin

Count per Day

Archives

This site is powered by:

Bookmarks

My Coding Page

Top Posts & Pages

My Skills

My Poster/Presentations

My Videos

My Bookshelf

Quote From Life

Caution and Tips:

Category

About Me & MyBlog

Recent Posts

Recent Comments

My Facebook

My Algorithmic Progress in OJ’s

My Github

My Linkedin

Tags

Count per Day

Archives

This site is powered by:

Bookmarks

My Coding Page

Top Posts & Pages

My Skills

My Poster/Presentations

My Videos

My Bookshelf

Quote From Life