CareerCup

superb solution

use min heap of size n .take top element every time and insert next element in the same list which the top element is belong to. O(nlogn) complexity extra space O(n+n)for linear array and O(n ) for min heap

approximation algorithm good approach

take the list which has minimum element start from first element element1 on list1 and have an index for both of other list now move one by one to find the nearest value of element1 in list2 and list3 find max(i,j,k)-min(i,j,k) store it in result now take element2 from list1 and move index on list2 and list3 to find the nearest of element2 now again find max(i,j,k)-min(i,j,k) if it is less than result then replace result.repeat to end of element in list1 return the result value .if u need the element value then maintain i,j,k when result is replaced.the complexity of worst case is O(sizeoflist1+sizeoflist2+sizeof3) space c omplexity is constant

is this push and pop O(1) implementation ?

int giMask[100],giNoCom;

void printCombination(int piList[],int piLenList)
{
	giNoCom++;
	cout<<"{ ";
	for(int liLocalIndex=0;liLocalIndex<=piLenList;liLocalIndex++)
	{
		if(giMask[liLocalIndex]==1)
		{
			cout<<" "<<piList[liLocalIndex]<<" ";
		}
	}
	cout<<" } "<<endl;
}
void PrintPermutation(int piList[],int piCurrIndex,int piLenList,int piCount)
{
	piCount--;
	if(piCount)
	{
		giMask[piCurrIndex]=1;
		for(int liLocalIndex=piCurrIndex+1;liLocalIndex<=piLenList;liLocalIndex++)
		{
			if((piLenList-liLocalIndex+1)>=piCount)
			PrintPermutation(piList,liLocalIndex,piLenList,piCount);
		}
		giMask[piCurrIndex]=0;
	}
	else if(piCount==0)
	{
		giMask[piCurrIndex]=1;
		printCombination(piList,piLenList);
		giMask[piCurrIndex]=0;
	}
}

int main()
{
	int liList[]={6,2,4,8,9,10,16,20};
	int liListLen=7,licount=4;
	for(int liLocalIndex=0;liLocalIndex<=liListLen;liLocalIndex++)
	{
		PrintPermutation(liList,liLocalIndex,liListLen,licount);
	}
	cout<<"the total no of combination is "<<giNoCom<<endl;
	return 0;
}
is this fine ?

hope this will work if not let me know thanks
int mask[100][100];
int liMaxLength,x,y;
void ClearMask()
{
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<4;j++)
		{
			{
				mask[i][j]=0;
			}
		}
	}
}
void PrintMask()
{
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<4;j++)
		{
			{
				cout<<" "<<mask[i][j]<<" ";
			}
		}
		cout<<endl;
	}
	cout<<"the count is "<<liMaxLength<<endl;
}
bool SnakeLength(int a[][4],int i,int j,int count)
{
	bool flag=false;
	count++;
	if(i+1<x &&(a[i+1][j]==a[i][j]+1))
	{
		if(SnakeLength(a,i+1,j,count))
		{
			flag=true;
		}
	}
	if(i-1 > -1 &&(a[i-1][j]==a[i][j]+1))
	{
		if(SnakeLength(a,i-1,j,count))
		{
			flag=true;
		}
	}
	if(j+1<y &&(a[i][j+1]==a[i][j]+1))
	{
		if(SnakeLength(a,i,j+1,count))
		{
			flag=true;
		}
	}
	if(j-1 > -1 &&(a[i][j-1]==a[i][j]+1))
	{
		if(SnakeLength(a,i,j-1,count))
		{
			flag=true;
		}
	}
	if(liMaxLength<count)
	{
		ClearMask();
		liMaxLength=count;
		flag=true;
	}
	if(flag)
	{
		mask[i][j]=1;
		return true;
	}
	return false;
}
int main()
{
	int a[4][4]=		{
		2, 3, 4, 5,
		4, 5, 10, 11,
		20, 6, 9, 12,
		6, 7, 8, 40
						};
	x=y=4;
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<4;j++)
		{
			if(mask[i][j]!=1)
			SnakeLength(a,i,j,0);
			PrintMask();
		cout<<endl<<endl;
		}
	}
	PrintMask();

	return 0;
}

but my design is not suitable for duplicate value

check out my solution i designed it for only unique value but its working for this input .my solution is not suitable for duplicate value in case of duplicate we need to find the minimum value in the list in O(n)and return the index

karthik ur solu is O(n) but do binary search will give you O(logn)

yes your right in case of more subsequent query urs is efficient thanks for suggestion

my design
given no is n
n%26 store it in array one by one until it n become zero for example given no is 702 then
array[0]=702%26 is 0
702/26=27
now array[1]=27%26 is 1
27/26 =1
now array[2]=1%26 is 1
1/26 is 0
take array[2]array[1]array[0]which is 1 1 0 now subtract one from all but last will give you 0 0 0 now print AAA
another example 323
will give 12 11 subtract by one but last gives 11 11 which is LL thats all

void FindNextHigherPalindrom(int piValue)
{
	int lstrValue[15];
	int liIndex=0;
	for(int liTempValue=piValue;liTempValue;liIndex++)
	{
		lstrValue[liIndex]=liTempValue%10;
		liTempValue/=10;
	}
	if(lstrValue[liIndex/2]<=lstrValue[liIndex/2-1])
	{
		if(lstrValue[liIndex/2]==9)
		{
			int liLocal;
			for(liLocal=liIndex/2;lstrValue[liLocal]==9&&liLocal<liIndex;liLocal++)
			{
				lstrValue[liLocal]=0;
			}
			if(liLocal==liIndex)
			{
				lstrValue[liIndex++]=1;
			}
			else
			{
				lstrValue[liLocal]++;
			}
		}
		else
		{
			lstrValue[liIndex/2]++;
		}
		int liLocal;
		if(liIndex%2==0)
		{
			liLocal=liIndex/2-1;
		}
		else
		{
			liLocal=liIndex/2;
		}
		for(int liLocal1=liIndex/2;liLocal>=0;liLocal--,liLocal1++)
		{
			lstrValue[liLocal]=lstrValue[liLocal1];
		}
	}
	for(int i=0;i<liIndex;i++)
	cout<<lstrValue[i];
}
let me know if there is any bug in this

int FindIndexOfRotation(int a[],int start,int end)
{
	if(start == end-1)
	{
		if(a[start]<a[end])return start;
		return end;
	}
	int mid=(start+end)>>1;
	if(a[start]<a[mid])
	{
		if(a[start]<a[end])
			return start;
		else
			return FindIndexOfRotation(a,mid,end);
	}
	else if(a[mid]<a[end])
	{
		return FindIndexOfRotation(a,start,mid);
	}
	else
		return mid;
}
let me know any bug in this

time complexity o(nlogn)

2 3 4 5
4 5 10 11
20 6 9 12
6 7 8 40
how come the output : 4 5 6 7 8 9 10 11 12
y not 2 4 5 6 7 8 9 10 11 12 40

take a[52][26] as extra space
now take first element in b[26][26] (given array) say index i=0,j=0 (consider the value inside this array as 0-25 instead of a-z) for example if b[0][0]='c';(here c considered as 'c'-'a'-1=2)
now assign a[0][2]=1 and a[26][2]=1 do like this for entire given array while filling in array a[][] if already it is 1 then the value is repeating if not the given array is perfectly valid.
give your suggestions