alok.net
BAN USERmain()
{
// int arr[] = {2,3,-5,4,8,-2,-10,-30, 20, 30,-50,10};
int arr[] = {-2,-3,-5,-4,-8,-1,-10,-30, -20, -30,-50,-10};
int sum =-100;
int s_index =0;
int e_index =0;
int maxsum=-100;
int max_s =0;
int max_e =0;
int i;
int n = sizeof(arr)/sizeof(arr[0]);
for( i=0; i < n ; i++)
{
sum += arr[i];
if(sum > maxsum)
{
maxsum = sum;
max_e =i;
max_s =s_index;
}
else if(sum < 0)
{
sum =0;
s_index = i+1;
}
}
printf("\nOriginal Array\n");
printf("{");
for(i=0; i < n ; i++)
{
printf("%d, ", arr[i]);
}
printf("}\n");
printf("\nOP Array\n");
printf("{");
for(i=max_s; i < max_e +1 ; i++)
{
printf("%d, ", arr[i]);
}
printf("}\n");
}
best sol would be if a swap gets minimized and in one shot the elements gets reolcation to right position.
for example : if we have array of size 6 and 4 shifts has to be done then
a[(i+s)%n] = a[i]
a[0] =a[4]
a[4] = a[2]
a[2] =a[0]
and so on
number of actual shift s = k % n
for( i=0 ; i < n/3 ; i++)
{
temp = a[i];
for(j=1; j < 4 ; j++)
{
next = ( i + j*s)%n
//swap the contents of a[next] and temp
temp1 = a[next]
a[next] = temp
temp = temp1
}
}
instead of using hash for the matrix, if we use hash of the search string the woud be gr8. so first we scan the search array in hash to see the occurance of every char in the search string then would travers the matrix one by one and indexing every occuranc of char in the search hash . if char is found that means char for search sring is found we decrement the count initially mainained. now if either at the end of inbetween all the count gets zero meansstring is found.
- alok.net November 09, 2013since there is no space restriction i will counting sort to get the elements present in the array and
#include <stdio.h>
#include<string.h>
#define range 500
int main()
{
int a[] = {40,50,11,32,55,68,75};
int b[sizeof(a)/sizeof(a[0])] ={-1,};
int c[range] ={-1,};
int i=0;
int flag =0;
int count =0;
int num=0;
memset(c,-1,range*4);
memset(b,-1,sizeof(a)/sizeof(a[0])*4);
for(i=0;i<(sizeof(a)/sizeof(a[0])) ; i++)
{
c[a[i]] =i;
}
for (i=0; count<(sizeof(a)/sizeof(a[0])); i++)
{
if(c[i] !=-1 && flag ==-1)
{
num =i;
flag =c[i];
printf("\nSearching element =%d index %d",num,flag);
}
else if(c[i] !=-1 && flag !=-1)
{
if(i > num)
{
int k=flag;
count++;
b[flag] = i;
num = i;
flag = c[i];
printf("\nmatch b[%d]=%d and next searching element =%d index =%d",k,i,num,flag);
}
}
}
printf("\nOriginal input\n");
printf("{ ");
for(i=0; i<sizeof(a)/sizeof(a[0]) ; i++)
{
printf("%d, ",a[i]);
}
printf(" }\n");
printf("\nNew Output\n");
printf("{ ");
for(i=0; i<sizeof(a)/sizeof(a[0]) ; i++)
{
printf("%d, ",b[i]);
}
printf(" }\n");
}
Approach could be to pop the element of binary tree in post order traversal so that to have leaf nodes first , and insert it in BST maintaining the property.
- alok.net December 06, 2013