SPOJ-2916::Can you answer these queries V

http://www.spoj.com/problems/GSS5/

Typical problem statement can be seen as below.

Problem: Given a array of numbers a[1...n] , and a Query(x1,y1,x2,y2).
Query(x1,y1,x2,y2) = Max { A[i]+A[i+1]+...+A[j] ; x1 <= i <= y1 , x2 j <= y2 and x1 <= x2 , y1 <= y2 }.

Lets analyze this query...
Wait a minute...!!
    Have you read my post on GSS1 problem ??
    Have you ever Solved GSS1 problem ??
If your answer is NO, then I suggest you to do that problem first.
http://code.karumanchi.me/2013/07/spoj-1043can-you-answer-these-queries-i.html


Here two cases araises based on {x1 <= i <= y1 , x2 j <= y2 and x1 <= x2 , y1 <= y2 }.
 Case-1: (x1,y1) and (x2,y2) doesn't overlap.
 Case-2: (x1,y1) and (x2,y2) overlaps.

Case-1::No Overlapping
 result would be (x1,y1).bestRightSum + (y1+1,x2-1).Sum +(x2,y2).bestLeftSum;

Case-2::No Overlapping
 result would be max of
   {
   (x1,x2-1).bestRightSum  + (x2,y2).bestLeftSum,
   (x1,y1).bestRightSum  + (y1+1,y2).bestLeftSum,
   (x2,y1).bestSum
   }




Implementation of the Same - Solution

// =====================================================================================
//       Filename:  GSS5.cpp
//    Description:
//         Author:  BrOkEN@!
// =====================================================================================
#include<cassert>
#include<cctype>
#include<climits>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<bitset>
#include<deque>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<fstream>
#include<iostream>
#include<sstream>
#include<streambuf>
#include<algorithm>
#include<iterator>
#include<new>
#include<string>
#include<utility>

template< class T >
inline T maxOfThree(T a, T b, T c){
    return max(max(a,b),c);
}

#define FOR(i,a,b) for(typeof((a)) i = (a); i <= (b) ; ++i )
#define REV_FOR(i,b,a) for(typeof((b)) i = (b); i >= (a) ; --i )
#define FOREACH(it,x) for(typeof((x).begin()) it=((x).begin()); it != ((x).end()); ++it)
#define REV_FOREACH(it,x) for(typeof((x).rbegin()) it=((x).rbegin()); it != ((x).rend()); ++it)


using namespace std;

typedef pair<int,int> PI;
typedef vector<PI> VI;

typedef struct node{
    int bestLeftSum,bestRightSum,Sum,bestSum;
   
    node merge(node& l,node& r){
        bestLeftSum = max(l.bestLeftSum,l.Sum+r.bestLeftSum);
        bestRightSum = max(l.bestRightSum+r.Sum,r.bestRightSum);
        Sum = l.Sum + r.Sum;
        bestSum = maxOfThree(l.bestSum,r.bestSum,l.bestRightSum+r.bestLeftSum);
    }
   
    node setNode(int val){
        bestLeftSum = bestRightSum = Sum = bestSum = val;
    }
       
} node;


const int MAX = 1<<14;

node T[MAX<<1];
int A[MAX];

void init(int Node,int i,int j){
    if(i==j){
        T[Node].setNode(A[i]);
        return;
    }else{
        int m = (i+j)/2;
        init(2*Node,i,m);
        init(2*Node+1,m+1,j);
        T[Node].merge(T[2*Node],T[2*Node+1]);
    }
}

node range_query(int Node,int i,int j,int L,int R){
    if(L > R) return T[0];
    if(i==L && R==j){
        return T[Node];
    }else{
        int m = (i+j)/2;
        if(R<=m){
            return range_query(2*Node,i,m,L,R);
        }else if(L>m){
            return range_query(2*Node+1,m+1,j,L,R);
        }else{
            node resultNode,left,right;
            left = range_query(2*Node,i,m,L,m);
            right = range_query(2*Node+1,m+1,j,m+1,R);
            resultNode.merge(left,right);
            return resultNode;
        }
    }
}

int query(int N,int x1,int y1,int x2,int y2){
    int result =0;
    if(y1<x2){
        result += range_query(1,0,N-1,x1,y1).bestRightSum;
        result += range_query(1,0,N-1,y1+1,x2-1).Sum;
        result += range_query(1,0,N-1,x2,y2).bestLeftSum;
    }else{
        result += maxOfThree(
                    range_query(1,0,N-1,x1,x2-1).bestRightSum  + range_query(1,0,N-1,x2,y2).bestLeftSum,
                    range_query(1,0,N-1,x1,y1).bestRightSum  + range_query(1,0,N-1,y1+1,y2).bestLeftSum,
                    range_query(1,0,N-1,x2,y1).bestSum
                    );
           
    }
    return result;
}

int main(){
    int T=0;
    scanf("%d",&T);

    int N=0,Q=0,x1=0,y1=0,x2=0,y2=0;
    FOR(t,1,T){
        scanf("%d",&N);
        FOR(i,0,N-1){scanf("%d",&A[i]);}
        init(1,0,N-1);
        scanf("%d",&Q);
        FOR(q,1,Q){
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            --x1;--y1;--x2;--y2;
            printf("%d\n",query(N,x1,y1,x2,y2));
        }
    }

    return 0;
}

SPOJ-1043::Can you answer these queries I

http://www.spoj.com/problems/GSS1/

Typical problem statement can be seen as below.

Problem: Given a array of numbers a[1...n] , and a query range [x,y].
query(x,y) should return the sub-sequence sum, whose sum is maximum in the interval [x,y].

Lets analyze this query.
Query(x,y) is the maximum of below values where sum(i,j) = a[i]+a[i+1]+......+a[j];

sum(x,x)	sum(x,x+1)	sum(x,x+2)	..........	sum(x,y-1)	sum(x,y)
	sum(x+1,x+1)	sum(x+1,x+2)	..........	sum(x+1,y-1)	sum(x+1,y)
		sum(x+2,x+2)	..........	sum(x+2,y-1)	sum(x+2,y)
			..........	..........	..........
				sum(y-1,y-1)	sum(y-1,y)
					sum(y,y)

Seriously whats wrong with coloring -we will come to that part.

Blue::The Color of Left Sum.
Where the range starts at 'x' but ends at any where in [x,y].

sum(x,x)	sum(x,x+1)	sum(x,x+2)	..........	sum(x,y-1)	sum(x,y)
	sum(x+1,x+1)	sum(x+1,x+2)	..........	sum(x+1,y-1)	sum(x+1,y)
		sum(x+2,x+2)	..........	sum(x+2,y-1)	sum(x+2,y)
			..........	..........	..........
				sum(y-1,y-1)	sum(y-1,y)
					sum(y,y)

Red::The Color of Right Sum.
Where the range starts at somewhere in [x,y] and ends at 'y'.

sum(x,x)	sum(x,x+1)	sum(x,x+2)	..........	sum(x,y-1)	sum(x,y)
	sum(x+1,x+1)	sum(x+1,x+2)	..........	sum(x+1,y-1)	sum(x+1,y)
		sum(x+2,x+2)	..........	sum(x+2,y-1)	sum(x+2,y)
			..........	..........	..........
				sum(y-1,y-1)	sum(y-1,y)
					sum(y,y)

Grey::The Color of Sum of the Elements.
Simply sum of all elements in interval [x,y].

sum(x,x)	sum(x,x+1)	sum(x,x+2)	..........	sum(x,y-1)	sum(x,y)
	sum(x+1,x+1)	sum(x+1,x+2)	..........	sum(x+1,y-1)	sum(x+1,y)
		sum(x+2,x+2)	..........	sum(x+2,y-1)	sum(x+2,y)
			..........	..........	..........
				sum(y-1,y-1)	sum(y-1,y)
					sum(y,y)

Green::The Color of nested Query ;).
Well, you can see this as the Query(x+1,y-1).

sum(x,x)	sum(x,x+1)	sum(x,x+2)	..........	sum(x,y-1)	sum(x,y)
	sum(x+1,x+1)	sum(x+1,x+2)	..........	sum(x+1,y-1)	sum(x+1,y)
		sum(x+2,x+2)	..........	sum(x+2,y-1)	sum(x+2,y)
			..........	..........	..........
				sum(y-1,y-1)	sum(y-1,y)
					sum(y,y)

Now, you can understand why i had to use these colors.


Lets maintain 4 values.
 bestLeftSum  - Best of all the Left Sums
 bestRightSum  - Best of all the Right Sums
 Sum  - Sum of all the elements
 bestSum  - well we need this to store resultSum of each query (Nested Query ;))
Logically, Query(x,y).resultSum = max (bestLeftSum,bestRightSum,sum,Query(x+1,y-1).bestSum);

But still the nested query stuff isn't so good O(N^2) :'(.
Why can't we use a tree(SegmentTree) ?? Why not a O(logN) for query??

Lets call the above info {bestLeftSum,bestRightSum,Sum,bestSum} as QueryNode.
and given information about QueryNode(L,M) and QueryNode(M+1,R).

Can't you be able to determine the QueryNode(L,R) with above information??
 QueryNode(L,M) -> l
 QueryNode(M+1,R) -> r

 Then For QueryNode(L,R),
  bestLeftSum = max (l.bestLeftSum,l.Sum+r.bestLeftSum);
  bestRightSum = max (l.bestRightSum+r.Sum,r.bestRightSum);
  Sum = l.Sum+r.Sum;
  bestSum = max(l.bestSum,r.bestSum,l.bestRightSum+r.bestLeftSum);

How?? - Check below graphical representation 



Implementation of the Same - Solution

// =====================================================================================
//       Filename:  GSS1.cpp
//    Description:  
//        Created:  05/23/2013 06:41:42 PM
//         Author:  BrOkEN@!
// =====================================================================================
#include<fstream>
#include<iostream>
#include<sstream>
#include<bitset>
#include<deque>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
#include<iterator>
#include<string>
#include<cassert>
#include<cctype>
#include<climits>
#include<cmath>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>

#define FOR(i,a,b) for(typeof((a)) i=(a); i <= (b) ; ++i)
#define FOREACH(it,x) for(typeof((x).begin()) it=(x).begin(); it != (x).end() ; ++it)

using namespace std;

typedef pair<int,int> PI;
typedef vector<PI> VI;

inline int max2(int a, int b) {return ((a > b)? a : b);}
inline int max3(int a, int b, int c) {return max2(a, max2(b, c));}

const int MAX = 1 << 16;
int a[MAX];

struct node
{
    int Sum,bestLeftSum,bestRightSum,bestSum;
    
    node split(node& l, node& r){
    } // No Need of Split Function
    
    node merge(node& l, node& r)
    {
        Sum = l.Sum + r.Sum;
        bestLeftSum = max( l.Sum + r.bestLeftSum , l.bestLeftSum );
        bestRightSum = max( r.Sum + l.bestRightSum , r.bestRightSum );
        bestSum = max( max( l.bestSum , r.bestSum) , l.bestRightSum + r.bestLeftSum );
    }
    
    node setValue(int val){
        Sum = bestLeftSum = bestRightSum = bestSum = val;
    }
};

node T[MAX << 1];

void init(int Node, int i, int j) {
    if(i==j) { // Initialize Leaf Nodes
        T[Node].setValue(a[i]);
        return;
    }else{ // Summerize Descendant Nodes Nodes
        int m = (i+j)/2;
        init(2*Node, i, m);
        init(2*Node+1, m+1, j);
        T[Node].merge(T[2*Node],T[2*Node+1]);
    }
}

void update(int Node, int i, int j,int idx, int val) { 
// Update element with index 'idx' in the range [i,j]
    if(i==j && i == idx) { // Update the LeafNode idx
        T[Node].setValue(val);
        return;
    }else{ // Summerize Descendant Nodes Nodes
        int m = (i+j)/2;
        if(idx <=m)
            update(2*Node, i, m, idx, val);
        else
            update(2*Node+1, m+1, j, idx, val);
        T[Node].merge(T[2*Node],T[2*Node+1]);
    }
}

void range_query(node& resultNode,int Node,int i, int j, int L, int R){ // Search for Node having interval info [L,R] in [i,j]; (i<=L<R<=j)
    if(i==L && j==R){
        resultNode = T[Node];
        return;
    }else{
        int m = (i+j)/2;
        if(R<=m)
            range_query(resultNode, 2*Node,  i, m, L, R);
        else if(L>m)
            range_query(resultNode, 2*Node+1, m+1, j, L, R);
        else{
            node left, right;
            range_query(left, 2*Node,  i, m, L, m);
            range_query(right, 2*Node+1, m+1, j, m+1, R);
            resultNode.merge(left,right);
        }
    }
}


int solve(){

    return 0;
}


int main(){

    int N=0,M=0;
    node res;
    scanf("%d",&N);
    FOR(i,0,N-1){
            scanf("%d", &a[i]);
    }
    init(1, 0, N-1);
    scanf("%d",&M);
    int x,y;
    FOR(i,0,M-1){
            scanf("%d%d",&x,&y);
                range_query(res, 1, 0, N-1, --x, --y);
                printf("%d\n", res.bestSum);
    }

    return 0;
}

SPOJ-1557::Can you answer these queries II

This is one of the difficult problems that i have solved. So i've decided to write an article about how to solve this problem.

Logically the problem statement is exactly like below.

Problem: Given a array of numbers a[1...n] (where duplicates are allowed), and a query range [x,y].
query(x,y) should return the sub-sequence sum, whose sum is maximum in the range [x,y] by satisfying uniqueness criteria.

Assume that a[x...y] is a sub-sequence having unique elements(i.e. with out duplicates).
Lets analyze the query asked for this range.
Query for range {x...y} can be expressed as below, assuming that all the queries {query(i,j) where j<y} were answered already.

query(x,y) =  max {
                 b(x,y),
                b(x+1,y),
                b(x+2,y),
                .
                ..
                ...
                b(y,y)
            }

where b(i,j) is defined as below.

b(i,j) = max {
            a[i],
            a[i]+a[i+1],
            a[i]+a[i+1]+a[i+2],
            ......
            a[i]+a[i+1]+a[i+2]+......+a[j]
        }

Lets go little further, do some sample calculations based on n values.

n-value	possible Queries	b-elements
1	query(1,1)	b(1,1)
2	query(1,1),query(1,2) query(2,2)	b(1,1),b(1,2) b(2,2)
3	query(1,1),query(1,2),query(1,3) query(2,2),query(2,3) query(3,3)	b(1,1),b(1,2),b(1,3) b(2,2),b(2,3) b(3,3)

So you might have already observed the pattern that we are looking for.
Now Formal definitions of query(x,y) and b(i,j).

query(x,y) -> is the sub-sequence sum, whose sum is maximum in all sub-sequences by satisfying uniqueness criteria.
b(i,j)     -> is the maximum sub-sequence in the range[i...j] by satisfying uniqueness criteria.

Algorithm:
    Create an array/segment Tree as 'b'. (Segment tree is suggested, will explain that later)
    For i = 1 to N
        ->update the 'b' by inserting the element a[i].
        ->Answer all the queries query(x,y) where x<=y and y=i. 

How to handle repeativeness of the elements ??

 Assume that a[j] is the element to be inserted, 
           a[j] will make its contribution towards the elements b(i,j) {where i<=j}.
 Insertion operation is done based on the assumption that, 
           all the elements in the range a[i...j] will be unique.

 Lets assume that there is an element a[m] {where i <= m <= j} which is duplicate of a[j].
 By our theory, a[m] might have already made contribution towards the elements b(i,m) {where i<=m}.
 so elements b(k,j)  {where m+1 <= k <= j} can include a[j] which is unique for them now.

 In Other words, a[j] can make contribution to the elmements b(k,j) 
             {where m+1 <= k <= j and m-is the last know position of a[j].}
 i.e
 a[j] can be updated in the range b(last[a[i]]+1,j) which preserves our uniqueness condition.        

Complexity of the Query. ??

    To calculate each b(i,j), logN operations are required.(Worst case).
    To find max of b(i,j), for a query it will take y-x+1 no.of calulations under that element.

    ** b(i,j) is calculated based on below, so total j-i+1 child element calculations.
    {b(i+0,i+0), b(i+0,i+1), b(i+0,i+2).........b(i+0,j)
               b(i+1,i+1), b(i+1,i+2).........b(i+1,j)
                             b(i+1,i+2).........b(i+1,j)
                                      ...........
                                       b(j,j)}

    Total Complexity = O(N) = (j-i+1)O(logN) = O((j-i+1)*logN);
    worst case O(NlogN).
    *** Save the processing time by updating child elements by maintaining a segment Tree. 
        So the complexity will come down to O(logN)

How to maintain the Segment Tree Node.??

/*
    Suppose a[j] is to be updated.
    Please be aware that all the queries with y<j are already Calculated before hand.
    So update the tree only to maintain the queries where y==j.

    i.e. At a certain point of time, after updating a[j],
        Leaf Nodes: will contain info about the range queries required query(1,j),query(2,j),query(3,j).....query(j,j).
        Non-Leaf Nodes: will contain info about controling interval mentioned below them.

    So maintain 4-values at each node.
*/

    struct node{
        int max;  //-> Indicates maximum sum in the interval.
        int evermax;  //-> Indicates maximum sum the history of this range.
        int change;   //-> Indicates the value to be modified in the given range.
        int everchange; //-> Indicates the value to be modified in the history of this range.
    };

For example take the below input.

4
4 -2 3 -2

Inserting the A[4] = -2 in the sequence, the tree will look like.

                        (5,5,0,0)
        (5,5,0,0)                (3,3,-2,0)
(0,0,5,5)       (0,0,1,1)       (0,0,3,3)       (0,0,0,0)

Look at the Leaf nodes, these nodes will address these queries with y==4. May be you can name them as result nodes. :D

                        (5,5,0,0)
        (5,5,0,0)                (3,3,-2,0)
(0,0,5,5)       (0,0,1,1)       (0,0,3,3)       (0,0,0,0)
 q(1,4)          q(2,4)          q(3,4)          q(4,4)  

Look at the Non-Leaf nodes, they will have the control information(change,everchange), may be you can name them as control nodes. ;)

                        (5,5,0,0) -> control the interval (1,4)
        (5,5,0,0)              (3,3,-2,0)
   control the interval (1,2)      control the interval (3,4) -> -2 will be included in (3,4) range only
(0,0,5,5)       (0,0,1,1)       (0,0,3,3)       (0,0,0,0) 

Operations required:
You might have figured out that, after inserting a elment a[j] we are no longer looking at queries query(x,y) where y<j.
Hence we are updating the childrens with the current values as they are being updated.
so Operations required will be,

        updateChilds(node& left,node& right)//with the current insertion values(i.e changes required are propagated.)
        clearNode()                     // Clear the non-Leaf nodes.
        updateNode(node& left,node& right)  // Make control nodes are also capable of mataining the result information.
        setNode(int val)                 //Set result nodes to the respective values.

Following is my code,for which i have got AC after 20 attempts :P.
Be sure to look out for 'long long' ;)

// =====================================================================================
//       Filename:  _GSS2.cpp
//    Description:  
//        Created:  07/25/2013 08:42:25 PM
//         Author:  BrOkEN@!
// =====================================================================================
#include<fstream>
#include<iostream>
#include<sstream>
#include<bitset>
#include<deque>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
#include<iterator>
#include<string>
#include<cassert>
#include<cctype>
#include<climits>
#include<cmath>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>

#define TIMER 0
#define FOR(i,a,b) for(typeof((a)) i=(a); i <= (b) ; ++i)
#define FOREACH(it,x) for(typeof((x).begin()) it=(x).begin(); it != (x).end() ; ++it)
template< class T > inline T _max(const T a, const T b) { return (!(a < b) ? a : b); }


using namespace std;

const int MAX = 100001;
const int INF = 0x7f7f7f7f;
//const int INF = 0;

typedef pair<int,int> PI;
typedef vector<PI> VI;
typedef long long int __int;

typedef struct node
{
    __int max,evermax,change,everchange;
    
    node split(node& l, node& r){
    } // No Need of Split Function
    
    node updateChilds(node& l, node& r){
        l.everchange = _max(l.everchange,l.change+everchange);
        l.change += change;
        r.everchange = _max(r.everchange,r.change+everchange);
        r.change += change;
    }
    
    node setNode(int val){
        change += val;
        everchange = _max(change,everchange);
    }
    node clearNode(){
        change = 0;
        everchange = -INF;
    }
    node updateNode(node& l, node& r){
        max = _max(_max(l.max,l.evermax+l.everchange),_max(r.max,r.evermax+r.everchange));
        evermax = _max(l.evermax+l.change,r.evermax+r.change);
    }
    
} node;

typedef struct query{
    int l,r,p;
} query;

int a[MAX],lastp[MAX<<1],lastq[MAX];
__int ans[MAX];
node T[1<<18];
query q[MAX];


void update(int node, int i, int j, int a, int b, int val) {
    if(a <= i && j <= b) {
            T[node].setNode(val);
    }
    else {
        int m = (i + j)/2;
        T[node].updateChilds(T[2*node],T[2*node+1]);
        T[node].clearNode();
        if(a <= m) update(2*node, i, m, a, b, val);
        if(m < b) update(2*node+1, m+1, j, a, b, val);
        T[node].updateNode(T[2*node],T[2*node+1]);
    }
}

__int range_query(int node, int i, int j, int a, int b) {
    if(a <= i && j <= b){
        return _max(T[node].max,T[node].evermax + T[node].everchange);
    }
    else {
        int m = (i + j)/2;
        T[node].updateChilds(T[2*node],T[2*node+1]);
        T[node].clearNode();
        T[node].updateNode(T[2*node],T[2*node+1]);
        return _max((a <= m ? range_query(2*node, i, m, a, b) : -INF), 
                    (m < b ? range_query(2*node+1, m+1, j, a, b) : -INF));
    }
}

int main(){

    int N=0;    
    scanf("%d",&N);
    FOR(i,1,N){    
        scanf("%d", &a[i]);    
    }
    
    int M=0;    
    scanf("%d",&M);
    FOR(i,1,M){
            scanf("%d%d",&q[i].l,&q[i].r);
            q[i].p = lastq[q[i].r];
     lastq[q[i].r]=i;
    }

    FOR(i,1,N){
        update(1, 1, N, lastp[a[i]+100000] + 1, i, a[i]);
        lastp[a[i]+100000] = i;
        for(int j=lastq[i];j;j=q[j].p){
                ans[j]=range_query(1, 1, N, q[j].l, q[j].r);
        }
    }

    FOR(i,1,M){printf("%lld\n", ans[i]);}
    


    return 0;
}

Linked List Related

Brief list of simple problems based on linked list and their solutions.
Most of them are recursive approaches and they can be written iteratively also.

1.Given a linked-list and 2 integers k & m. Reverse the linked-list till k elements and then traverse till m elements and repeat.
2.Reverse a Linked List(Recursion and Iterative methods).
3.Print Linked List in Reverse & Alternative nodes.

#include<iostream>
#include<sstream>
#include<string>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<vector>

using namespace std;



struct node{
 int data;
 struct node *next;
};


void push(struct node **head_first,int data){
 struct node *new_node=NULL;
 new_node=(struct node*)malloc(sizeof(struct node));
 
 new_node->data=data;
 new_node->next=(*head_first);
 *head_first=new_node;
}

void printAll(struct node *head){
 while(head!=NULL){
  cout<<head->data<<"\t";
  head=head->next;
 }
}

void printInReverse(struct node *head){
 if(head==NULL){
  return;
 }
 printInReverse(head->next);
 cout<<head->data<<"\t";
}

void printAlternative(struct node *head){
 if(head==NULL){
  return;
 }
 cout<<head->data<<"\t";
 if(head->next!=NULL){
  printAlternative(head->next->next);
 }
}

struct node* reverseListRecursion(struct node** head_first,struct node** head){
 
 struct node *curr=(*head_first);
 
 if(curr->next==NULL){
  *head=curr;
  return curr;
 }
 
 struct node **next=NULL;
 next=&(curr->next);
 
 reverseListRecursion(next,head)->next=curr;
 
  
 return curr;
}

struct node* reverseListIteration(struct node* head){
 if(head!=NULL){
  struct node* prevN=NULL;
  struct node* currN=head;
  struct node* nextN=head->next;
  
  while(nextN!=NULL){
   currN->next=prevN;
   prevN=currN;
   currN=nextN;
   nextN=nextN->next;
  }
  currN->next=prevN;
  return currN;
 }
}


struct node* reverseList(struct node** root,struct node** head,struct node** revHead,int i,int k){
    if(root==NULL && i<k){
        return NULL;
    }
    
    if(i==k){
        (*head)=(*root)->next;
 (*revHead)=(*root);
        return *root;
    }
    
    struct node* curr=*root;
    struct node* nextN=reverseList(&(curr->next),head,revHead,i+1,k);
    if(nextN!=NULL){
        nextN->next=curr;
    }else{
        return NULL;
    }
    
    if(i==1 && *head !=NULL){
        curr->next=(*head);
        return *head;
    }
    
    return curr;
}

void reverseAndTraverse(struct node *root, int k,int m){
    struct node *kNode=NULL; // K th Node - Assuming Node count from 0 :P
    struct node *revHead=NULL;

    kNode=reverseList(&root,&kNode,&revHead,1,k);
    
    if(kNode==NULL){
        printf("InSufficient Linked List\n");
        return;
    }
    
    int i=0;
    while(i<m && kNode!=NULL){
        printf("%d ",kNode->data);
        kNode=kNode->next;
 i++;
    }    

 cout<<endl; 

  while(revHead!=NULL){
  printf("%d ",revHead->data);
  revHead=revHead->next;
 }
}



int main(){
 struct node *head=NULL;
 
 push(&head,6);
 push(&head,5);
 push(&head,4);
 push(&head,3);
 push(&head,2);
 push(&head,1);
 
 
 cout<<"Printing In Normal:\t";
 printAll(head);cout<<endl;
 
 cout<<"Printing In Reverse:\t";
 printInReverse(head);cout<<endl;

 cout<<"Printing In Alternative:\t";
 printAlternative(head);cout<<endl;
 
 cout<<"Converting to Reverse:\n";
 struct node* revHead=NULL;
 reverseListRecursion(&head,&revHead)->next=NULL; 
 head=revHead;
 
 cout<<"After the Reversal-1:\t";
 printAll(head);cout<<endl;
 
 cout<<"Converting to Reverse Again:\n";
 head=reverseListIteration(head); 
 
 cout<<"After the Reversal-2:\t";
 printAll(head);cout<<endl;
 
 cout<<"Perform Reverse of K and Traversal of M \t";
 int n=1;
 scanf("%d",&n);
 reverseAndTraverse(head,n,3);cout<<endl;

 
}

Create a list of Vertical sum of a given binary tree.

A simple recursive solution would be sufficient enough to solve this.

The approach is to weight each node in the tree as below, starting with root node's weight as 0.

1. Weight of the left child of the node will be less than weight of the root by one.
2. Weight of the right child of the node will be more than weight of the root by one.

By this way the whole tree can be weighted,
and now Sum up all the nodes with same weight which gives the vertical sum of the column of nodes.

Below is implementation, and the results can be stored in either array or list or any DS.

/*
Q: Create a list of Vertical sum of a given binary tree.
*/

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

int getHeightOfTree(struct node* root){
 if(root==NULL){
  return -1;
 }
 int l= getHeightOfTree(root->left);
 int r= getHeightOfTree(root->right);
 return ((l>r)?(l+1):(r+1));
}


void buildVerticalSum(struct node* root, int A[], int h, int w){
 if(root!=NULL){
  buildVerticalSum(root->left,A,h,w-1);
  A[h+w]+=root->data;
  buildVerticalSum(root->right,A,h,w+1);
 }
}

/* Array A will have vertical sums of the tree. This can be modified to create a list. Or in Other DS*/
void verticalSum(struct node* root){
 int h=getHeightOfTree(root);
 
 int* A=NULL;
         A=(int*)malloc(sizeof(int)*(2*h+1));
 
 buildVerticalSum(root,A,h,0);
 
 for(int i=0;i<2*h+1;i++){
  printf(“%d ”,A[i]);
 }
 printf(“\n”); 
 
}

Given a String of Length N, find all combinations of substrings of length k(Repetition Allowed)

Print all combination of given length k possible with characters available in a given string "S" with repetition in new lines.
Again an easy recursion problem.

void printAllCombinationsOfLengthK(char in[],int n,char* out,int k,int l){
	if(k==l){
		printf("%s\n",out);
		return;
	}
	for(int i=0;i<n;i++){
		out[l]=in[i];
		printAllCombinationsOfLengthK(in,n,out,k,l+1);
	}
}

int main(){
    ios_base::sync_with_stdio(false);
	
	char* a="abcdef";
	int k=3;
	char op[k]; // Output string of length K
	
	printAllCombinationsOfLengthK(a,strlen(a),op,k,0);

    system("PAUSE");
}

Define the tree, such that the parent node always contains the sum of children nodes.

Simple. I think, no explanation is required for this.

Get summation values of right sub-tree and left sub-tree, and add them to current node's data and update.

/*Define the tree, such that the parent node always contains the sum of children nodes.*/
int sumUp(struct node *root){
 if(root==NULL){
  return 0;
 }else{
  int l=sumUp(root->left);
  int r=sumUp(root->right);
  root->data=root->data + l + r;
  return root->data;
 }
}

Change the structure of a Tree node to hold a pointer for the next in-order element (sucessor).

Idea is simple, based on Threaded Trees concept.
We need to modify Morris In-Order Traversal algorithm a little to convert the tree into a linked list, where each node's right pointer will point to its in-order successor.

There is no need to change the current tree node structure.

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

/*Tree to InOrder list conversion*/
struct node*  MorrisInOrderConversion(struct node* root){
 struct node *curr,*pre,*head=NULL;
 
 if(root==NULL){
  return NULL;
 }
 
 curr=root;
 
 while(curr!=NULL){
  if(curr->left==NULL){
   if(head==NULL){
    head=curr;
   }
   curr=curr->right;
  }else{
   pre=curr->left;
   
   while(pre->right!=NULL && pre->right!=curr){
    pre=pre->right;
   }
   
   if(pre->right==NULL){
    pre->right=curr;
    curr=curr->left;
   }else{
    struct node* next=curr->right;
    struct node* temp=curr->right;
    curr->right=NULL;
    while(next->left!=NULL){
     next=next->left;
    }
    curr->right=next;
    curr=temp;
   }
  }
 }
 
 return head; //Returns head of the converted list
}

/*Traverse the Converted list*/
void traverseList(struct node* head){
 while(head!=NULL){
  printf("%d ",head->data);
  head=head->right;
 }
}

And One more approach also exists for this, which involves creating a new list without changing current tree structure.

This can be written with Morris In-Order Tree traversal algorithm or Generic In-Order traversal algorithm.

Below is the code for generic traversal algorithm.

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

/*New Node structure defined*/
struct iNode{
 struct node* pNode;
 struct iNode* successor;
};

/*Tree to InOrder List - Start */
void insertINode(struct node* p){
 struct iNode *temp = (struct iNode*)malloc(sizeof(struct iNode));
 temp->pNode=p;
 temp->successor=NULL;
 
 if(iHead==NULL){
  iHead=temp;
 }else{
  iList->successor=temp;
 }
 iList=temp; 
};

void inOrderList(struct node* root){
 if(root!=NULL){
  inOrderList(root->left);
  insertINode(root);
  inOrderList(root->right);
 }
};

void traverseIList(){
 struct iNode *curr=iHead; 
 while(curr!=NULL){
  printf("%d ",curr->pNode->data);
  curr=curr->successor;
 }
}
/*Tree to InOrder List - End */

InOrder Traversal of Tree with out using Stack and Recursion

The idea is to create links to root from predecessor node in the left sub-tree for each node.
When traversal on the current node in done, move to the right child and make that node as current node and follow the same procedure.

1. Start from the root of the current tree, as current node.
2. If current node's left Child is NULL
        print the node data.
        make right of the current node as current.
    else
        If right child of the right most node of the left sub-tree is NULL
           make it as a link to current node.
           make left of the current node as current.
        else
           print the current node data.
           make right of the current node as current.

void MorrisInOrderTraversal(struct node* root){
 struct node *curr,*pre;
 if(root==NULL){
  return;
 }
 
 curr=root;
 
 while(curr!=NULL){
  if(curr->left==NULL){
   printf("%d ",curr->data);
   curr=curr->right;
  }else{
   pre=curr->left;
   
   while(pre->right!=NULL && pre->right!=curr){
    pre=pre->right;
   }
   
   if(pre->right==NULL){
    pre->right=curr;
    curr=curr->left;
   }else{
    pre->right=NULL;
    printf("%d ",curr->data);
    curr=curr->right;
   }
  }
 }
}

Max values of Sliding Window of K, in an Array of length N(>K)

Q: An array of size N is given. Array is sub divided into sub array of size K. Find maximum value of each sub array.

It is sliding window. Let array be “1 2 3 4 5 6” and k=2
then Sub arrays {1 2},{2 3},{3 4},{4 5},{5 6}.

For all these sub arrays, maximum of each needs to found.[Array is unordered.]

struct node{ 
 int data, index; 
 struct node next; 
 struct node *prev; 
}; 

struct DQueue{ 
 struct node *front; 
 struct node *rear; 
}; 

struct DQueue createDQ(){ 
 struct DQueue* newNode=(struct DQueue*)malloc(sizeof(struct DQueue)); 
 newNode->front=newNode->rear=NULL; 
} 

bool isDQEmpty(struct DQueue* DQ){ 
 return (DQ->front==NULL); 
} 

struct node* createNode(int data,int index){ 
 struct node* newDQNode=(struct node*)malloc(sizeof(struct node)); 
 newDQNode->data=data; 
 newDQNode->index=index; 
 return newDQNode; 
} 

void pushDQFront(struct DQueue* DQ,int data,int index){ 
 struct node* temp=createNode(data,index); 
 if(DQ->front==NULL && DQ->rear==NULL){ 
  DQ->front=DQ->rear=temp; 
 }else{ 
  temp->next=DQ->front; 
  DQ->front->prev=temp; 
  DQ->front=temp; 
 } 
} 

void pushDQBack(struct DQueue* DQ,int data,int index){ 
 struct node* temp=createNode(data,index); 
 if(DQ->front==NULL && DQ->rear==NULL){ 
  DQ->front=DQ->rear=temp; 
 }else{ 
  DQ->rear->next=temp; 
  temp->prev=DQ->rear; 
  DQ->rear=temp; 
 } 
} 

void popDQFront(struct DQueue* DQ){ 
 if(isDQEmpty(DQ)){ 
  return; 
 } 
 struct node* temp=DQ->front; 
 if(DQ->front==DQ->rear){ 
  DQ->front=DQ->rear=NULL; 
 }else{ 
  DQ->front->next->prev=NULL; 
  DQ->front=DQ->front->next; 
  temp->next=NULL; 
 } 
 free(temp); 
 temp=NULL; 
} 

void popDQBack(struct DQueue* DQ){ 
 if(isDQEmpty(DQ)){ 
  return; 
 } 
 struct node* temp=DQ->rear; 
 if(DQ->front==DQ->rear){ 
  DQ->front=DQ->rear=NULL; 
 }else{ 
  DQ->rear->prev->next=NULL; 
  DQ->rear=DQ->rear->prev; 
  temp->prev=NULL; 
 } 
 free(temp); 
 temp=NULL; 
} 

struct node* frontOfDQ(struct DQueue* DQ){ 
 if(isDQEmpty(DQ)){ 
  return NULL; 
 } 
 return DQ->front; 
} 

struct node* rearOfDQ(struct DQueue* DQ){ 
 if(isDQEmpty(DQ)){ 
  return NULL; 
 } 
 return DQ->rear; 
} 

void maxSlidingWindow(int a[],int n,int k){ 
 int i; 
 struct DQueue* DQ=createDQ(); 

 for(i=0;i<k;i++){ 
  while(!isDQEmpty(DQ) && a[i] >= rearOfDQ(DQ)->data){ 
   popDQBack(DQ); 
  } 
  pushDQBack(DQ,a[i],i); 
 } 
 printf("%d",frontOfDQ(DQ)->data); 

 for(;i<n;i++){ 
  while(!isDQEmpty(DQ) && frontOfDQ(DQ)->index <= i-k){ 
   popDQFront(DQ); 
  } 
  while(!isDQEmpty(DQ) && a[i] >= rearOfDQ(DQ)->data){ 
   popDQBack(DQ); 
  } 
  pushDQBack(DQ,a[i],i); 
  printf("%d",frontOfDQ(DQ)->data); 
 } 
} 

int main(){ 
 int a[]={3,5,2,8,2,3,7,9,2,2,44,66,2,23,4,54,2}; 
 int n=sizeof(a)/sizeof(a[0]); 
 int k=4; 
 maxSlidingWindow(a,n,k); 
 system("PAUSE"); 
}

Find two elements which will sum up to a given value, in a Sorted Array.

Given sorted integer array and a given value we have to find two elements which will sum up to a given value.

Since it is a sorted array our job is so easy.

For example, array a is having n element in sorted order
A[0]<A[1]<A[2]<........<A[n-1];

From this we can deduce that,
A[0]+A[1]<A[0]+A[2]<A[0]+A[3].......;
A[0]+A[n-1]<A[1]+A[n-1]<.....<A[n-2]+A[n-1];

Compare from the extreme summations with the given value and increase or decrease the indexes according to the comparison.

Int a[SIZE];
Int a[SIZE];
int n;

void findTwoElementsToN(int a[],int n){
 int i=0;
 int j=sizeof(a)/sizeof(int) -1;
 int sum=0;

 if(i<j){
  sum=a[i]+a[j];
  if(sum<n){
   i++;
  }else if(sum>n){
   j--;
  }else{
    printf(“%d and %d”,a[i],a[j]);
  }
 }
}

Least Common Ancestor of two nodes in a Given Unordered Tree.

There can be three possibilities for finding LCA is a tree.
1. Both nodes belong to left sub-tree.
2. Both nodes belong to right sub-tree.
3. One per each sub-tree.
 In fact 4th possibility is also there, i.e. nodes are not at all present in the tree.

In the first case, Current node can't be the LCA because an CA exist in the left sub-tree.
Similarly, in the second case, Current node can't be the LCA because an CA exist in the right sub-tree.
In the third case, Current node will be the LCA.

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

struct node* leastCommonAncestor(struct node* root,struct node* p,struct node* q){
 
 if(root==NULL){
  return NULL;  //If no root  leastCommonAncestor is NULL.
 }

 if(root==p || root==q){
  return root; // Check if the current root is equal to any of the desired node.
 }else{
  struct node* l=leastCommonAncestor(root->left, p, q); // Find LCA in left of the tree
  struct node* r=leastCommonAncestor(root->right, p, q); // Find LCA in right of the tree
  
  if(l!=NULL && r!=NULL){
   return root; 
  }else if(l!=NULL && r==NULL){
   return l;
  }else if(l==NULL && r!=NULL){
   return r;
  }else{
   return NULL;
  }
 } 
}

Binary Tree Related

Code for the following Questions can be found in below code.

Q: Given a node of Binary Tree . find all node's at distance k from it .
Q: Simple InOrder, PreOrder, PostOrder Traversals of the Tree.
Q: Given a node in the Tree. Find path from the root of tree to the node.
Q: Given a node in the Tree. Find the height of the node from the root.

/*
Written By BrOkEN@!

Q: Given a node of Binary Tree . find all node's at distance k from it .
Q: Simple InOrder,PreOrder,PostOrder Traversals of the Tree.
Q: Given a node in the Tree. Find path from the root of tree to the node.
Q: Given a node in the Tree. Find the height of the node from the root.

*/

#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<cstdio>
#include<cstdlib>
#include<cstddef>
#include<cstring>
#include<cctype>
#include<cmath>
#include<cassert>
#include<climits>

#define INFINITE 1000000

using namespace std;

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

struct trackNode{
 struct node* pNode;
 struct trackNode* parent;
};

struct trackNode *list=NULL,*head=NULL;

void insertTrackNode(struct node* p){
 struct trackNode *temp = (struct trackNode*)malloc(sizeof(struct trackNode));
 temp->pNode=p;
 
 if(list==NULL){
  head=temp;
 }else{
  list->parent=temp;
 }
 list=temp; 
};

/*Find path from root to Specific Node*/
bool trackPath(struct node *root, struct node *p){
 
 if(root==NULL){
  return false;
 }
 
 if(root==p){
  insertTrackNode(root);
  return true;
 }else{
  if(trackPath(root->left,p)||trackPath(root->right,p)){
   insertTrackNode(root);
   return true;
  }else{
   return false;
  }
 }
};

/*Constructing a tree and returning the root*/
struct node* buildTree(){
 struct node* n01=(struct node*) malloc(sizeof(struct node));n01->data=1;
 struct node* n02=(struct node*) malloc(sizeof(struct node));n02->data=2;
 struct node* n03=(struct node*) malloc(sizeof(struct node));n03->data=3;
 struct node* n04=(struct node*) malloc(sizeof(struct node));n04->data=4;
 struct node* n05=(struct node*) malloc(sizeof(struct node));n05->data=5;
 struct node* n06=(struct node*) malloc(sizeof(struct node));n06->data=6;
 struct node* n07=(struct node*) malloc(sizeof(struct node));n07->data=7;
 struct node* n08=(struct node*) malloc(sizeof(struct node));n08->data=8;
 struct node* n09=(struct node*) malloc(sizeof(struct node));n09->data=9;
 struct node* n10=(struct node*) malloc(sizeof(struct node));n10->data=10;
 struct node* n11=(struct node*) malloc(sizeof(struct node));n11->data=11;
 struct node* n12=(struct node*) malloc(sizeof(struct node));n12->data=12;
 struct node* n13=(struct node*) malloc(sizeof(struct node));n13->data=13;
 struct node* n14=(struct node*) malloc(sizeof(struct node));n14->data=14;
 struct node* n15=(struct node*) malloc(sizeof(struct node));n15->data=15;
 
 n08->left=n04;n08->right=n12;
 
 n04->left=n02;n04->right=n06;
 n02->left=n01;n02->right=n03;
 n06->left=n05;n06->right=n07;
 
 n12->left=n10;n12->right=n14;
 n10->left=n09;n10->right=n11;
 n14->left=n13;n14->right=n15;
 
 n01->left=n01->right=NULL;
 n03->left=n03->right=NULL;
 n05->left=n05->right=NULL;
 n07->left=n07->right=NULL;
 n09->left=n09->right=NULL;
 n11->left=n11->right=NULL;
 n13->left=n13->right=NULL;
 n15->left=n15->right=NULL;

 
 return n08;
};

/*InOrder Traversal of Tree with root Node*/
void inOrder(struct node* root){
 if(root!=NULL){
  inOrder(root->left);
  printf("%d ",root->data);
  inOrder(root->right);
 }
};

/*PreOrder Traversal of Tree with root Node*/
void preOrder(struct node* root){
 if(root!=NULL){
  printf("%d ",root->data);
  preOrder(root->left);
  preOrder(root->right);
 }
};

/*PostOrder Traversal of Tree with root Node*/
void postOrder(struct node* root){
 if(root!=NULL){
  postOrder(root->left);
  postOrder(root->right);
  printf("%d ",root->data);
 }
};


/*Find Nodes at distance K from the root(possibility to skip subtree is also provided.)*/
void findNodesAtDistanceK(struct node *root,int k,bool left,bool right){
 
 
 if(root!=NULL){
  if(k==0){
   printf("%d ",root->data);
   return;
  }
  
  if(left==true && right==false){
   findNodesAtDistanceK(root->left,k-1,true,true);
  }else if(left==false && right==true){
   findNodesAtDistanceK(root->right,k-1,true,true);
  }else{
   findNodesAtDistanceK(root->left,k-1,true,true);
   findNodesAtDistanceK(root->right,k-1,true,true);
  }
 }
}

/*Get Height of the node*/
int getHeight(struct node* root,struct node* p){
 
 if(root==NULL){
  return INFINITE;
 }
 
 if(root==p){
  return 0;
 }else{
  int l=1+getHeight(root->left,p);
  int r=1+getHeight(root->right,p);
  if(l>r){
   return r;
  }else{
   return l;
  }
 }
}


int main(){
 int k=3;//Distance
 struct node *root=NULL;
 root=buildTree();
 
 struct node* p=root->right->left->right; //get a random node from Tree

 if(trackPath(root,p)){
  int i=0;
  struct trackNode* prev=NULL;
  while(head!=NULL && i<=k){

   if(prev==NULL){
    findNodesAtDistanceK(head->pNode,k-i,true,true);
   }else{
    findNodesAtDistanceK(head->pNode,k-i,head->pNode->left!=prev->pNode,head->pNode->right!=prev->pNode);
   }
   
   prev=head;
   head=head->parent;
   i++;
  }
 }

 system("PAUSE");
}

Maximum Sum Such that No Two Elements are Adjacent

Question: Given an array all of whose elements are positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array.
Ex-1:  3 2 7 10 should return 13 (sum of 3 and 10) .
Ex-2: 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).

Algorithm:

Loop for all elements in arr[] and maintain two sums incl and excl
where
      incl = Max sum including the previous element and
      excl = Max sum excluding the previous element.

Max sum excluding the current element will be max(incl, excl) and
max sum including the current element will be excl + current element
(Note that only excl is considered because elements cannot be adjacent).

At the end of the loop return max of incl and excl.

Explanation:

  arr[] = {5,  5, 10, 40, 50, 35}

  inc = 5
  exc = 0

  For i = 1 (current element is 5)
  incl =  (excl + arr[i])  = 5
  excl =  max(5, 0) = 5

  For i = 2 (current element is 10)
  incl =  (excl + arr[i]) = 15
  excl =  max(5, 5) = 5

  For i = 3 (current element is 40)
  incl = (excl + arr[i]) = 45
  excl = max(5, 15) = 15

  For i = 4 (current element is 50)
  incl = (excl + arr[i]) = 65
  excl =  max(45, 15) = 45

  For i = 5 (current element is 35)
  incl =  (excl + arr[i]) = 80
  excl = max(5, 15) = 65

And 35 is the last element. So, answer is max(incl, excl) =  80.

C++ Code:

    #include <iostream>

    using namespace std;
     
    int FindMax(int a[],int l){
        int incl=a[0];
        int excl=0;

        for(int i=1;i<l;i++){
            int excl_new=(incl>excl)?incl:excl;
            incl=excl+a[i];
            excl=excl_new;
        }

        return (incl>excl)?incl:excl;
    }
     
    int main(){
        int a[]={3,2,7,10};
        cout<<FindMax(a,4)<<endl;
    }

Converting Decimal to Hexa-Decimal

In this blog i will be writing all crap code for the questions asked in various interviews.

Starting with the following question.

How to convert a decimal number to its equivalent Hexa-decimal equivalent. Give a C/C++ code for the same.

Explanation and Algorithm :

If you don't know or Forgotten what is Decimal/Hex-Decimal Numbers, the following table will tell u that.

HEXADECIMAL	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
DECIMAL	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15

Steps:

1. Divide the decimal number by 16.   Treat the division as an integer division. 
2. Write down the remainder (in hexadecimal).
3. Divide the result again by 16.  Treat the division as an integer division. 
4. Repeat step 2 and 3 until result is 0.
5. The hex value is the digit sequence of the remainders from the last to first.

Example: Convert the number 188 DECIMAL to HEXADECIMAL

DIVISION	RESULT	REMAINDER (in HEX)
188 / 16	11	C (12 decimal)
11 / 16	0	B (11 decimal)
ANSWER		BC

C++ Code:

#include <iostream>

using namespace std;

int main(){
    int iDecimalNumber;
    cout<<"Enter a decimal number to convert it to Hex :";
    cin>>iDecimalNumber;
    cout<<"Its Hex Equivalent is: "<<hex<<iDecimalNumber<<endl;
}

C Code:

#include "stdio.h"

int main(){
    int iDecimalNumber;
    printf("Enter a decimal number to convert it to Hex :");
    scanf("%d",&amp;iDecimalNumber);
    printf("Equivalent Hexa-Decimal Number is :");
    printf("%X\n",iDecimalNumber);
}

Simple isn't it :P. you didn't like it ??.
You can go around the globe. Think smart :D.