jeetu.mfp
BAN USERLarge,medium,Small reffered as l,m,s respectively,sum=0
take the first three elements and store them in l,m,s such that largest of them is in l,2nd largest in m and the 3rd largest in s
also we are taking the sum of them
sum=l+m+s;
count=3;
do
{
scanf("%d",&a);
sum=sum+a;
if(a>s)
{
s=a;
if(s>m)
{
swap(s,m);
if(m>l)
swap(m,l);
}
}
count++;
}while(a!=0);
after input is terminated by occurence of first 0;
we have total sum=s, total count of no. of inputs,s,m,l.
avg=(sum-(s+m+l))/(count-3);
printf("first three numbers%d %d %d\n\n",l,m,s);
printf("avg=%d\n\n",avg);
this solves the purpose in O(n) and very less memory when all that is required to give top 3 nos and the avg of the remaining.
I have used the technique called PREFIXSUM where the values of the Sum for various entries are saved while taking the input only.
RS[i][j]=sum of all the elements of the ith row upto jth entry
CS[i][j]=sum of all the elements of the jth column upto ith row
S[i][j]=sum of the matrix formed by the rectangle formed by the points {1,1}to {i,j}
M[i][j]=value stored in the ith row jth column
sum=sum of any sub array of kXk length
and each is found in constant time only.
So the performance is optimised as it is O(n^2).
space complexity is too O(n^2) actually 4(n^2),as extra space used for storage of RS[n][n],CS[n][n],S[n][n].
but the time is as good as taking the inputs O(n^2)
also to find the exact sub matrix store the value of sum in another arrray of nXn and the value of this matrix which is highest will give the maximum sum for that which can be found through BOTTOM UP approach or say if sum[x][y] is the highest then corresponding sub matrix will be the subMatrix formed by the M[x-k+1][y-k+1] to M[x][y]
#include<stdio.h>
#include<conio.h>
int main()
{
int i,j,max=0,n,k,sum=0;
scanf("%d",&n);
int M[n][n],S[n][n],RS[n][n],CS[n][n],;
for(i=0;i<=n;i++)
{
M[i][0]=M[0][i]=S[i][0]=S[0][i]=RS[i][0]=RS[0][i]=CS[i][0]=CS[0][i]=0;
}
//this is to check boundary condition
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&M[i][j]);
RS[i][j]=RS[i][j-1]+M[i][j];
CS[i][j]=CS[i-1][j]+M[i][j];
S[i][j]=S[i-1][j-1]+RS[i][j]+CS[i][j]-M[i][j];
}
}
scanf("%d",&k);
//taken the size of sub matrix
for(i=k;i<=n;i++)
{
for(j=k;j<=n;j++)
{
sum=S[i][j]-S[i-k][j]-S[i][j-k]+S[i-k][j-k];
if(sum>max)
max=sum;
}
}
printf("%d\n",sum);
getch();
return 0;
}
this question can be done in O(1) space and in O(n) time too
1.scan the array from 1 to n one by one and as soon as you get a number(check absolute values of numbers) go to its index position and if the value stored in it is positive then multiply it by -1.
this way all the nos. which are present between 1-k would be having negative values stored in their indices while the numbers which are missing would be having positive values stored in their indices.
travel the array again from 1-k and print the value of indices that have positive values stored in it.
this works fine here as there are only positive integers present here :)
and also we save memory which was otherwise wasted in creating either Boolean or even array of size k
@crazydev I'm getting the sum done by subtracting through the indices of the matrices that are of kxk
- jeetu.mfp August 24, 2012read the code all has been explained it will work in O(n^2) time only!!!!