CareerCup

unsigned int greatest(unsigned int n) {
	unsigned int result = 0, digit1 = n % 10, digit2, sum = 0, multiplier = 1, newresult;

	n = n/10;
	while (n > 0) {
		digit2 = n % 10;
		if (digit1 == digit2) {
			newresult = n * multiplier + sum;
			if (newresult > result)
				result = newresult;
		}

		sum += digit1 * multiplier;
		digit1 = digit2;
		multiplier *= 10;
		n /= 10;
	}

	if (result == 0)
		printf("No consecutive digits");

	return result;
}

This solution uses a trie (or radix tree) to solve this problem. In a trie, each character represents an edge. Complexity to insert any user into this trie is O(m), where m is no. of characters in user's name. At the same time, we are also maintaining another sorted doubly linked list, logins, which keeps track of all login counts by every user, sorted from highest to lowest. Insertion complexity into this linked list is O(n), where n is no. of UNIQUE users. Printing top k users from logins list is O(t), where t is no. of entries in result.

#define CHILD_COUNT 128

typedef struct {
	struct node *child[CHILD_COUNT];
	unsigned int count;
	char *str;
} node;

typedef struct {
	unsigned int count;
	node *user;
	struct login *next;
	struct login *prev;
} login;

node *createnode() {
	node *n = (node *) calloc(1, sizeof(node));
	assert( n != NULL);

	unsigned int i;
	for (i = 0; i < CHILD_COUNT; i++)
		n->child = NULL;

	n->count = 0;
	n->str = NULL;
}

node *insert(node *head, char *str) {
	char *p = str;
	assert( str != NULL);

	while (*p != '\0' ) {
		if (head->child[*p] == NULL)
			head->child[*p] = createnode();

		head = head->child[*p];
		p ++;
	}

	if (head->str == NULL)
		head->str = strdup(str);

	head->count ++;
	return head;
}

void print_top_users(char *str, unsigned int k) {
	login * logins = NULL;
	node *head = createnode();

	construct_trie(head, &logins, str);
	print_logins(logins, k);

	free_trie(head);
	free_logins(logins);
}

void construct_trie(node *head, login **logins, char *str) {
	char *token = strtok(str, ',');
	while (token != NULL) {
		node *n = insert(head, token);
		logins = update_logins(*logins, n);
		token = strtok(NULL, ',');
	}
}

login *update_logins(login *logins, node *n) {
	login *p = find_login(logins, n);
	if (p == NULL) {
		p = (login *) calloc(1, sizeof(login));
		assert(p != NULL);
		
		p->count = 1;
		p->user = n;
		p->next = p->prev = NULL;
	} else {
		logins = delete_login(logins, p);
	}

	p->count = n->count;
	logins = insert_login(logins, p);
	return logins;
}

login *find_login(login *logins, node *n) {
	login *p = logins;
	while (p != NULL) {
		if (p->user == n) 
			return p;
		p = p->next;
	}
	return NULL;
}

login *delete_login(login *logins, login *p) {
	if (logins == p)
		logins = logins->next;

	if (p->next != NULL)
		p->next->prev = p->prev;

	if (p->prev != NULL)
		p->prev->next = p->next;

	return logins;
}

login *insert_login(login *logins, login *p) {
	// logins list is empty, this is the first entry
	if (logins == NULL) {
		p->next = p->prev = NULL;
		return p;
	}

	login *q = logins, *r;
	while ((q != NULL) && (q->count > p->count)) {
		r = q;
		q = q->next;
	}

	// insert into last of logins list
	if (q == NULL) {
		r->next = p;
		p->prev = r;
		p->next = NULL;
		return logins;
	}

	// insert into middle or start of logins list
	p->next = q;
	p->prev = q->prev;
	q->prev = p;
	if (p->prev != NULL)
		p->prev->next = p;

	return logins;
}

void print_logins(login *logins, unsigned int k) {
	while ((logins != NULL) && (k != 0)) {
		printf("User: %s count: %u\n", logins->user->str, logins->count);
		if ((logins->next != NULL) && (logins->next->count < logins->count))
			k --;

		logins = logins->next;
	}
}

void free_trie(node *head) {
	if (head == NULL)
		return;

	if (head->str != NULL) {
		free(head->str);
		head->str = NULL;
	}

	unsigned int i;
	for (i = 0; i < CHILD_COUNT; i ++) 
		free_trie(head->child[i]);

	free(head);
	head = NULL;
}

void free_logins(login * logins) {
	if (logins == NULL) 
		return;

	free_logins(logins->next);
	free(logins);
	logins = NULL;
}

This solution iterates thourgh all combinations of quote triplets. For each triplet, either it is included in final solution, or it is not. The solution evaluates both paths for each triplet and comes up with a minimum cost solution.

typedef struct {
	int f;
	int l;
	double c;
} quote;

typedef struct {
	int f;
	int l;
} range;

quote add(quote q1, quote q2) {
	if ((q1.f <= q2.f) && (q1.l >= q2.l))
		return q1;

	if ((q1.f >= q2.f) && (q1.l <= q2.l))
		return q2;

	// ranges are not inclusive of each other
	quote result;
	result.f = (q1.f < q2.f) ? q1.f : q2.f;
	result.l = (q1.l > q2.l) ? q1.l : q2.l;
	result.c = q1.c + q2.c;
	return result;
}

double min_cost(quote q[], unsigned int n, range r) {
	if ((n == 0) || (r.f > r.l))
		return -1;

	quote p;
	p.f = r.l;
	p.l = r.f;
	p.c = 0;
	return get_min_cost(q, n, r, p);
}

double get_min_cost(quote q[], unsigned int n, range r, quote p) {
	if (n == 0)
		return -1;

	if ((p.f <= r.f) && (p.l >= r.l))
		return p.c;

	double c1 = get_min_cost(q + 1, n - 1, r, p);
	double c2 = get_min_cost(q + 1, n - 1, r, add(p, q[0]));
	if (c1 == -1)
		return c2;

	if (c2 == -1)
		return c1;

	return (c1 < c2) ? c1 : c2;
}

Here is a recursive solution.

void print_nonoverlap(int a[], unsigned int n) {
	if (n == 0)
		return;

	unsigned int *b = (unsigned int *) calloc(n, sizeof(unsigned int));
	if (b == NULL) {
		printf("Failed to allocate memory.");
		return;
	}

	print_no_intern(a, n, b, 0);
	free(b);
}

void print_no_intern(int a[], unsigned int n, unsigned int b[], unsigned int m) {
	unsigned int i;
	if (n == 0) {
		unsigned int start = 0, j;
		for (i = 0; i < m; i++) {
			printf("(");
			for (j = 0; j < b[i]; j ++)
				printf("%d", a[start ++]);
			printf(")");
		}
		printf("\n");
	}

	for (i = 1; i <= n; i ++) {
		b[m] = i;
		print_no_intern(a + i, n - i, b, m + 1);
	}
}

Lets view chess as a graph. Each square is a node in graph, and there are edges between nodes, if knight can directly go from one location to another. Our goal is to find the shortest path from start to end location in this graph.

I solved it by using a breadth first search in this graph. Taken a 8 X 8 array, marked start position with 0. All the squares where knight can reach from starting location are marked as 1. All the locations where knight can reach from 1 locations, were marked as 2. This process was repeated, until we get a no. in our end location. No. in end location denotes the no. of moves needed, and we can backtrace from there to find the path sequence for knight.

void print_path(unsigned int x1, unsigned int y1, unsigned int x2, unsigned int y2) {
	if ((x1 > 7) || ((x2 > 7) || (y1 > 7) || (y2 > 7))
		return;

	unsigned int a[8][8], i, j;
	for (i = 0; i < 8; i++)
		for (j = 0; j < 8; j ++)
			a[i][j] = 9999;
	
	a[x1][y1] = 0;
	i = 0;
	while (a[x2][y2] != 9999) {
		i ++;
		move(a, i);
	}

	print_backtrace(a, x2, y2, i);
}

void move(unsigned int a[][], unsigned int n) {
	unsigned int i, j, b[8][2], c, k;
	for (i = 0; i < 8; i ++) 
		for (j = 0; j < 8; j ++) {
			if (a[i][j] == n - 1) {
				c = get_moves(a, i, j, b);
				for (k = 0; k < c; k++) {
					if (a[b[k][0]][b[k][1]]  == 9999)
						a[b[k][0]][b[k][1]] = n;
				}
			}
		}

	return;
}

unsigned int get_moves(unsigned int a[][], unsigned int x, unsigned int y, unsigned int b[][]) {
	int i = x + 1, j = y + 2;
	unsigned int c = 0;
	
	if ((i < 8) && (j < 8)) {
		b[c][0] = i;
		b[c++][1] = j;
	}

	i = x + 1; j = y - 2;
	if ((i < 8) && (j >= 0)) {
		b[c][0] = i;
		b[c++][1] = j;
	}

	i = x - 1; j = y + 2;
	if ((i >= 0) && (j < 8)) {
		b[c][0] = i;
		b[c++][1] = j;
	}

	i = x - 1; j = y - 2;
	if ((i >= 0) && (j >= 0)) {
		b[c][0] = i;
		b[c++][1] = j;
	}

	i = x + 2; j = y + 1;
	if ((i < 8) && (j < 8)) {
		b[c][0] = i;
		b[c++][1] = j;
	}

	i = x + 2; j = y - 1;
	if ((i < 8) && (j >= 0)) {
		b[c][0] = i;
		b[c++][1] = j;
	}

	i = x - 2; j = y + 1;
	if ((i >= 0) && (j < 8)) {
		b[c][0] = i;
		b[c++][1] = j;
	}

	i = x - 2; j = y - 1;
	if ((i >= 0) && (j >= 0)) {
		b[c][0] = i;
		b[c++][1] = j;
	}

	return c;
}

void print_backtrace(unsigned int a[][], unsigned int x, unsigned int y, unsigned int n) {
	if (n == 0) {
		printf("[%u, %u]\n", x, y);
		return;
	}

	unsigned int b[8][2], c, i;
	c= get_moves(a, x, y, b);
	for (i = 0; i < c; i ++) {
		if (a[b[i][0]][b[i][1]] == n - 1) {
			print_backtrace(a, b[i][0], b[i][1], n - 1);
			break;
		}
	}

	printf("[%u, %u]\n", x, y);
}

bool X86IsCanonicalAddress(void *a) {
	void *b = 0xffff000000000000;
	if ((a & b) == b)
		return true;

	if ((a ^ b) & b == b)
		return true;

	return false;
}

int set_bit_l_to_r(int x, int y, int l, int r) {
	int i;
	for (i = l; i <= r; i++)
		if (get-bit(x, i))
			y = set-bit(y, i);

	return y;
}

int get-bit(int x, unsigned int b) {
	return x & (1 << b);
}

int set-bit(int y, unsigned int b) {
	return y | (1 << b);
}

Here is the solution using dynamic programming. It only calculates jumbled numbers from 10 to 99. Rest all answers can be obtained by using previous results. X is a jumbled number, if its last 2 digits are jumbled number, and first n-1 digits are jumbled numbers.

void print_jumbled(unsigned int N) {
	bool *a = (bool *) calloc (1, N);
	if (a == NULL) {
		printf("Failed to allocate memory.");
		return;
	}

	unsigned int i;
	for (i = 1; i < N; i++)
		if (jumbled(a, i))
			printf("%u ", i);

	free(a);
}

bool jumbled(bool a[], unsigned int n) {
	if (n < 10) {
		a[n] = true;
		return true;
	}

	if (n < 100) {
		unsigned int first = n % 10;
		unsigned int second = (n/10) % 10;
		if ((first == second) || (first + 1 == second) || (first == second + 1)) {
			a[n] = true;
			return true;
		}
		a[n] = false;
		return false;
	}

	a[n] = a[n % 100] && a[n/10];
	return a[n];
}

Complexity is O(log n) for both operations, building road and checking if the road exists.

Algorithm:
* Create DAGs (Directed Acyclic Graph) of road connectivity
* If two cities are part of same DAG, they are connected, otherwise not
* Find DAG root of both cities, if root is same for both, they are connected.
* If they have different roots, and we are building a road, connect both the DAGs, now all the cities in both DAGs are connected to each other.

class RoadNetwork {
	private:
		unsigned int n, *parent;
		unsigned int root(unsigned int x);

	public:
		void buildRoad(unsigned int a, unsigned int b);
		bool isRoadExists(unsigned int a, unsigned int b);

		RoadNetwork(unsigned int n) {
			this.n = n;
			parent = (unsigned int *) calloc (n, sizeof(unsigned int));
			if (parent == NULL)
				printf("Failed to allocate memory");
			else {
				unsigned int i;
				for (i = 0; i < n; i ++)
					parent[i] = n;
			}
		}

		~RoadNetwork() {
			free(parent);
		}
}

void RoadNetwork::buildRoad(unsigned int a, unsigned int b) {
	unsigned int r1 = root(a);
	unsigned int r2 = root(b);

	if (r1 == r2)
		return;
	parent(r1) = r2;
}

void RoadNetwork::isRoadExists(unsigned int a, unsigned int b) {
	if (root(a) == root(b))
		return true;
	return false;
}

unsigned int RoadNetwork::root(unsigned int x) {
	while (parent[x] != n)
		x = parent[x];
	return x;		
}

A recursive solution:

void print_jumbled(unsigned int n) {
	unsigned int i;
	for (i = 1; i < n; i++)
		if (jumbled(i))
			printf("%u ", i);
}

bool jumbled(unsigned int n) {
	if (n < 10)
		return true;

	unsigned int first = n % 10;
	n = n / 10;
	unsigned int second = n % 10;
	if ((first == second) || (first + 1 == second) || (first == second + 1))
		return jumbled(n);

	return false;
}

This simple solution has worst-case complexity O(n*n), but average case is O(n).

* Start from left, first element is pivot point
* Skip the number, if it is greater than pivot, pivot's maxPrefix would be more than this.
* Skip the last few numbers, when we can't get a better maxPrefix than current one.

int max-maxPrefix(int a[], int n) {
	int temp, i;
	if (n <= 0)
		return -1;

	int result = maxPrefix(a, 0, n);
	int pivot = a[0];

	for (i = 1; i < n - 1; i ++) {
		if (a[i] >= pivot)
			continue;

		if (n - i - 1 <= result)
			break;

		temp = maxPrefix(a, i, n);
		if (temp > result) {
			result = temp;
			pivot = a[i];
		}
	}
	return result;
}

int maxPrefix(int a[], int index, int n) {
	int result = 0, i;
	for (i = index + 1; i < n; i ++)
		if (a[i] > a[index])
			result ++;

	return result;
}

A simple recursive solution:

void print_nums(int n) {
	for(q = 0; q < n; q++)
		print_intern(0, 0, 0, q, n);
}

void print_intern(int x, int next_pos, int bits, int cur_len, int total_len) {
	if (bits >= cur_len) {
		printf("%d\n", x);
		return;
	}

	for(j = next_pos; j < total_len; j++) {
		y = set_bit(x, j);
		print_intern(y, j + 1, bits + 1, cur_len, total_len);
	}
}

* Create a min-heap, also storing original location of each element. Min-heap is a data structure, which stores minimum element at top, insertion/removal complexity is log(n).
* Pop elements one by one, if their new index differs more than k from original, push them to end, otherwise push them in sorted array.
* Time complexity: O(n * log(n)), Space: O(n)

tuple t;
for (i = 0; i < n; i++) {
	t.n = a[i];
	t.pos = i;
	min-heap.insert(t);
}

start = 0, end = n - 1;
for (i = 0; i < n; i++) {
	t = min-heap.pop();
	if (start + k > t.pos)
		a[start++] = t.n;
	else
		a[end--] = t.n;	
}

The man bought 3 digits "6", "0", and "0". One digit was for $1, 3 digits for $3.

@Erasmus

Middle node may not always contain middle of string. Consider the list,

"abcdefghi"->"i"->"h"->"g"->"f"->"e"->"d"

typedef struct _Work
{
	string name;
	string start;
	string end;

	_Work( string name1, string start1, string end1 )
	{
		name = name1;
		start = start1;
		end = end1;
	}

	_Work()
	{
		name = "";
		start = "00:00";
		end = "00:00";
	}
}Work;


vector<Work> sortWorks( vector<Work> input )
{
	vector<Work> output;

	while( input.size() > 0 )
	{
		int min_index = 0;
		for( unsigned int i = 1; i < input.size(); i++ )
		{
			if( input[i].start.compare( input[min_index].start ) < 0 )
				min_index = i;
		}
		output.push_back( input[min_index] );
		input.erase( input.begin() + min_index );
	}

	return output;
}

vector<Work> maxDay;
int maxMinutes;

vector<Work> getNextPossibleCandidates( Work w, vector<Work> remaining )
{
	vector<Work> output;
	string starttime = w.start;
	string endtime = "";

	for( int i = 0; i < remaining.size(); i++ )
	{
		if( endtime.empty() )
			endtime = remaining[i].end;

		if( remaining[i].start.compare( endtime ) > 0 )
			break;

		output.push_back( remaining[i] );
	}

	return output;
}

int getMinutes( Work w )
{
	int start = atoi( w.start.substr( 0, 2 ).c_str() ) * 60 + atoi( w.start.substr( 3, 2 ).c_str() );
	int end = atoi( w.end.substr( 0, 2 ).c_str() ) * 60 + atoi( w.end.substr( 3, 2 ).c_str() );

	return end-start;
}

void maximizeSchedule( vector<Work> tillNow, vector<Work> remaining )
{
	Work lastWork;
	if( tillNow.size() > 0 )
		lastWork = tillNow[tillNow.size() - 1];

	vector<Work> candidates = getNextPossibleCandidates( lastWork, remaining );
	if( candidates.size() == 0 )
	{
		int thisValue = 0;
		for( int i = 0; i < tillNow.size(); i++ )
			thisValue += getMinutes( tillNow[i] );

		if( ( maxDay.size() == 0 ) || ( thisValue > maxMinutes ) )
		{
			maxDay = tillNow;
			maxMinutes = thisValue;
		}
	}

	for( int i = 0; i < candidates.size(); i++ )
	{
		vector<Work> tempTillNow = tillNow;
		vector<Work> tempRemaining = remaining;

		int j = 0;
		for( j = 0; j < remaining.size(); j++ )
		{
			if( remaining[j].start.compare( candidates[i].end ) > 0 )
				break;
		}
		tempTillNow.push_back( candidates[i] );
		tempRemaining.erase( tempRemaining.begin(), tempRemaining.begin() + j );
		maximizeSchedule( tempTillNow, tempRemaining );
	}
}

void getMaxSchedule( vector<Work> v )
{
	vector<Work> tillNow;
	vector<Work> sorted = sortWorks( v );

	maximizeSchedule( tillNow, sorted );

}

1. Sort the work items by their start times.
2. Proceed the solution through backtracking.
3. At each stage, possible candidates are next item just after the last item, and all other work items overlapping with first item.
4. When all items are processed, compare them with max solution. If it is greater than Max, store this value in Max.

@AB

Subsequence need not be of only 3 elements. It can be of 1, 2, 3, 4 ... any number of consecutive elements.

@DaCritique

Can you please be more specific, why it won't work? Or, give any input anomaly where it won't work.

@Erasmus

Each node contains a string. Assume this list,

"abc" -> "defghi" -> "jk"

Now, how will your solution work?

@PseudoLife

Can you elaborate more on?

1. Reverse the DLL from its middle

How will you reverse, if middle is somewhere in between a string?

bool isPalindrome( Node *head )
{
	if( head == NULL )
		return true;

	Node *start = head;
	Node *end = head;
	while( end->next != NULL )
		end = end->next;

	int i = 0, j = end->value.length() - 1;

	while( ( start != end ) || ( i < j ) )
	{
		if( start->value.at( i ) != end->value.at( j ) )
			return false;

		i++;
		if( i >= start->value.length() )
		{
			i = 0;
			start = start->next;
			if( ( start == end ) && ( i == j ) )
				return true;
		}

		j--;
		if( j < 0 )
		{
			end = end->previous;
			j = end->value.length() - 1;
		}
	}

	return true;
}

1. Keep one pointer at start, another at end node
2. Compare first element of start with last element of end
3. If mismatch, return false
4. Otherwise, move start to next element, end to previous
5. If next/previous element does not exist, move to next/previous node and continue. Move them one by one and check exist condition
6. Exist condition, when both pointers are at same node same character

void printFromFile(string fileName, int percentage) 
{
	char buf[100];
	ifstream infile( fileName );

	while( !infile.eof() )
	{
		infile.read( buf, 100 );
		int count = infile.gcount();
		int to_print = (percentage*100)/count;
		int start = rand() % (count - to_print + 1);

		for( int i = 0; i < to_print; i++ )
			cout << buf[start + i];
	}

	infile.close();
}

1. Say, percent is given input from user.
2. Read 100 bytes from file
3. generate a random no. between 0 and 100-percent
4. Print percent bytes from randdom no.
5. Repeat this process untill you exhaust complete file.
6. In the last, bytes less than 100 will be read, adjust percent and random function accordingly.

void sortDuplicates( int a[], int n )
{
	sort( a, a + n );

	// create total array
	int *total = new int[n+1];
	int index = 1;
	total[0] = 0;
	total[1] = 1;
	for( int i = 1; i < n; i++ )
	{
		total[i+1] = 0;
		index = ( a[i] == a[i-1] ) ? index + 1 : 1;
		total[ index ]++;
	}

	// create commulative_index 
	int *commulative_index = new int[n+1];
	commulative_index[0] = 0;
	for( int i = 1; i < n; i++ )
		commulative_index[i] = commulative_index[i-1] + total[i];

	int *target = new int[n];
	target[0] = a[0];
	commulative_index[0]++;
	int group=0; 
	for( int i = 1; i < n; i++ )
	{
		if( a[i] != a[i-1] )
			group=0;
		else
			group++;

		target[commulative_index[group]++]=a[i];
	}

	for( int i = 0; i < n; i++ )
		cout << target[i] << " ";

	free( target );
	free( commulative_index );
	free( total );
}

1. Let us say input array, { 2,9,1,5,1,4,9,7,2,1,4 }
2. Sort the array, { 1,1,1,2,2,4,4,5,7,9,9 }
3. Scan the sorted_array, to count no. of items having one or more repetitions, two or more repetitions ...
4. This total array is { 6, 4, 1, 0, ... }. It means 6 items (1,2,4,5,7,9) have one or more repetitions, 4 items (1,2,4,9) have two or more repetitions, ....
5. Create a commulative_index from total array, {0,6,10,11,11,11...)

target[0] = sorted_array[0];
commulative_index[0]++;
group=0; 
for i = 1 to n-1
	if( sorted_array[i] != sorted_array[i-1] )
		group=0;
	else
		group++;

	target[commulative_index[group]]=sorted_array[i];


Time Complexity: nlogn (sorting) + n (scan) + n (create commulative_index) + n (store in target)
	= nlogn

Space Complexity: n (total) + n (commulative_index) + n (target) = 3n

@vgeek, let us take a simple case, {-1, -3, -5}

- For first two numbers, your code will go into first if condition, marking bin[1] and bin[4] as 1, count_trip as 3.
- For third number, it will go into second if condition, printing "Triplet exists ", which is incorrect.

bool isAnagram( char *s1, char *s2 )
{
	int map[255] = {0};

	if( ( s1 == NULL ) && ( s2 == NULL ) )
		return true;

	if( ( s1 == NULL ) || ( s2 == NULL ) )
		return false;

	while( *s1 != '\0' )
	{
		map[*s1]++;
		s1++;
	}

	while( *s2 != '\0' )
	{
		map[*s2]--;
		s2++;
	}

	for( int i = 0; i < 255; i++ )
	{
		if( map[i] != 0 )
			return false;
	}

	return true;
}

Node *traversalToTree( int preorder[], int inorder[], int n )
{
	Node *head = NULL;

	for( int i = 0; i < n; i++ )
		head = insert( head, preorder[i], inorder );

	return head;
}

int mycmp( int value1, int value2, int inorder[] )
{
	int pos1 = -1;
	int pos2 = -1;
	int i = 0;

	while( ( pos1 == -1 ) || ( pos2 == -1 ) )
	{
		if( inorder[i] == value1 )
			pos1 = i;

		if( inorder[i] == value2 )
			pos2 = i;

		i++;
	}

	return (pos1-pos2);
}

Node *insert( Node *head, int value, int inorder[] )
{
	Node *pNewNode = new Node();
	pNewNode->value = value;
	pNewNode->left = NULL;
	pNewNode->right = NULL;

	if( head == NULL )
		return pNewNode;

	Node *p = head;
	while( true )
	{
		int compare = mycmp( value, p->value, inorder );
		if( compare <= 0 )
		{
			if( p->left == NULL )
			{
				p->left = pNewNode;
				break;
			}
			else
				p = p->left;
		}
		else
		{
			if( p->right == NULL )
			{
				p->right = pNewNode;
				break;
			}
			else
				p = p->right;
		}
	}

	return head;
}

@vgeek, try this input {-1,-3,-5,4,11,-6}

It is only able to find one triplet {-1, -3, 4}, not second one {-5, 11, -6}.

void swap( int *arr, int pos1, int pos2 )
{
	std::cout << pos1 << " " << pos2 << std::endl;
	int temp = arr[pos1];
	arr[pos1] = arr[pos2];
	arr[pos2] = temp;
}

void swapWith0( int src[], int tgt[], const int n )
{
	int *now = new int[n];
	int i;

	for( i = 0; i < n; i++ )
		now[ src[i] ] = i;

	do
	{
		while( tgt[now[0]] != 0 )
			swap( now, 0, tgt[now[0]] );

		for( i = 0; i < n; i++ )
		{
			if( tgt[now[i]] != i )
			{
				swap( now, 0, i );
				break;
			}
		}
	}while( i < n );

	free( now );
}

There may not be a solution in all the cases. But if there exists, this code will print it out.

#define NUM_PURSES 7

void distribute( int total, int alreadyChosen )
{
	int result[NUM_PURSES] = {0};
	int currentTotal = 0;
	int next_count = 1;
	bool consumed = false;

	for( int i = 0; i < NUM_PURSES; i++ )
	{
		if( ( !consumed ) && ( next_count >= alreadyChosen ) )
		{
			next_count = alreadyChosen;
			consumed = true;
		}

		if( ( next_count + currentTotal ) > total )
			next_count = total - currentTotal;

		result[i] = next_count;
		currentTotal += result[i];
		next_count = currentTotal + 1;
	}

	for( int i = 0; i < NUM_PURSES; i++ )
		std::cout << result[i] << std::endl;
}

Try input, {-1, 4, -3, -2}

Your code will print out, "No triplet exists". While there exists a triplet of first 3 elements.

@Zoro, can you explain how did you reach the formula in step 4? I think, it should be (1/M)^(i-1) in the first part. See explanation below.

Base case, i=0.
Probability of an element hashing in a slot = 1/M
Probability of an element not hashing in a particular slot (ending in remaining M-1 slots) = (M-1)/M
All N elements not hashing in that slot = (M-1)/M * (M-1)/M * (M-1)/M ...
= ((M-1)/M)^N

Let us take the case of i=1.
First element can hash at any possible slot, probability = 1.
Now, probability of remaining N-1 elements not hashing in that particular slot = ((M-1)/M)^(N-1)


Let us take the case of i=2.
First element can hash at any possible slot, probability = 1.
Probability of second element going into same slot = 1/M
Now, probability of remaining N-2 elements not hashing in that particular slot = ((M-1)/M)^(N-2)
Probability of a slot having 2 elements = (1/M)*((M-1)/M)^(N-2)

To make it generic:

P(i) = ((M-1)/M)^N, when i=0
P(i) = (1/M)^(i-1) * ((M-1)/M)^N, otherwise

Here comes O(n) solution.

int maxSequenceCount( int a[], int n )
{
	int count[2] = {0};
	
	for( int i = 0; i < n; i++ )
	{
		count[ a[i] ]++;
	}
	
	int start = 0;
	int end = n - 1;

	while( ( start < end ) && ( count[0] != count[1] ) )
	{
		int more = ( count[0] < count[1] ) ? 1 : 0;
		if( a[start] == more )
		{
			start ++;
			count[more]--;
			continue;
		}

		if( a[end] == more )
		{
			end --;
			count[more]--;
			continue;
		}

		count[ a[start] ]--;
		start++;
	}

	return ( count[0] == count[1] ) ? 2 * count[0] : 0;
}

Here is O(n*n) solution.

int maxSequenceCount( int a[], int n )
{
	int result = 0;
	
	for( int i = 0; i < ( n - 1 ); i++ )
	{
		int count[2] = {0};
		
		for( int j = i; j < n; j++ )
		{
			count[ a[j] ]++;
			if( ( count[0] == count[1] ) && ( count[0] > result/2 ) )
				result = 2 * count[0];
		}
	}
	
	return result;
}

Thats right. I added "continuous" later to avoid any further confusion.

I think, for loop's end conditions need little correction.

i < l - 2
j < l - 1
k < l

This is not a subset sum problem. It is a subsequence sum problem.

That said, elements should be continuous in the array whose sum is 0.

void printTriplet(const int a[], int n)
{
    int result[n][n] = {0};
    
    for( int x = 0; x <= n ; x ++ )
    {
        for( int y = 0; y < n; y ++ )
            result[x][y] = MAXINT;
    }
    
    
    for( int i = 0; i < n; i ++ )
    {
        for( int x = 0; x <= i ; x ++ )
        {
            for( int y = i; y < n; y ++ )
            {
                if( result[x][y] == MAXINT )
                    result[x][y] = 0;
                    
                result[x][y] += a[i];
            }
        }
    }
    
    for( int x = 0; x <= n ; x ++ )
    {
        for( int y = 0; y < n; y ++ )
            if( result[x][y] == 0 )
                print( a, x, y );
    }
    
}

void print( int a[], int x, int y )
{
    printf("Triplet: ");
    for( int i = x; i <= y; i++ )
    {
        printf("%d ", a[i] );
    }
    printf("\n");
}

void printTriplet(const int a[], int n)
{
    for( int x = 0; x < n ; x ++ )
    {
        for( int y = 0; y < n; y ++ )
        {
            result[x][y] = a[x] + a[y];
            processed[x][y] = false;
    }
    
    int[] sortedArray = sort( a, n );
    
    for( int x = 0; x < n ; x ++ )
    {
        for( int y = 0; y < n - x; y ++ )
        {
            if( processed[x][y] )
                continue;
                
            processed[x][y] = true;
            int itemToLook = 0 - result[x][y];
            bool found = binarySearch( sortedArray, n, itemToLook );
            if( found )
            {
                int z = search( a, n, itemToLook );
                processed[y][x] = true;
                processed[x][z] = true;
                processed[y][z] = true;
                processed[z][x] = true;
                processed[z][y] = true;
                print( a[x], a[y], itemToLook );
            }
        }
    }
}

#define MAXLEN 100
#define MOD 1009
long possibleStrings[MAXLEN];

int calculate( string s, int pos )
{
	int len = s.length();
	if( pos == len )
		return 1;

	int result = 0;
	int chars = s.at( pos ) - 'a';
	if( ( pos > 0 ) && ( s.at( pos ) > s.at( pos - 1 ) ) )
		chars--;

	return ( ( chars * possibleStrings[ len - pos - 1] ) + calculate( s, pos + 1 ) ) % MOD;

}

int getSStringCount(string s)
{
	// initialize possibeStrings array
	possibleStrings[0] = 1;
	for( int i = 1; i < MAXLEN; i++ )
		possibleStrings[i] = ( possibleStrings[i-1] * 25 ) % MOD;

	return calculate( s, 0 );
}

N = input sources

int A[N];

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

{

    int ret = readNextValue( i, &A[i] );

    if( ret == NO_MORE_INPUTS )

    {

        A[i] = MAX_INT;

    }

}

int min_index;

do

{

    min_index = 0;

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

{

    if( A[i] < A[min_index] )

    {

        min_index = i;

    }

}   

    if( A[min_index] != MAX_INT )

{

writeIntoSortedArray( A[min_index] );

int ret = readNextValue( min_index, &A[min_index] );

    if( ret == NO_MORE_INPUTS )

    {

        A[min_index] = MAX_INT;

    }

}

} while( A[min_index] != MAX_INT );