sowmya.kp
BAN USERO(n) solution in C:
#include<limits.h>
#include<stdio.h>
#include<stdlib.h>
int* d;
void merge_arr(int a[],int b[],int c[],int a_size,int b_size,int c_size) {
int small=INT_MAX;
int i,j,k,l;
i=j=k=l=0;
int* p=d;
while(l<a_size+b_size+c_size) {
small=INT_MAX;
if(i!=a_size && a[i]<small)
small=a[i];
if(j!=b_size && b[j]<small)
small=b[j];
if(k!=c_size && c[k]<small)
small=c[k];
if(small==a[i]) i++;
if(small==b[j]) j++;
if(small==c[k]) k++;
d[l++]=small;
}
}
int main() {
int a[]={50,51,52};
int b[]={23,43,76,81};
int c[]={31,55};
int i;
int a_size=sizeof(a)/sizeof(a[0]);
int b_size=sizeof(b)/sizeof(b[0]);
int c_size=sizeof(c)/sizeof(c[0]);
d=(int*)malloc(a_size+b_size+c_size);
merge_arr(a,b,c,a_size,b_size,c_size);
for(i=0;i<(a_size+b_size+c_size);i++)
printf("%d\n",d[i]);
}
O(n) solution in C:
#include<limits.h>
#include<stdio.h>
#include<stdlib.h>
int* d;
void merge_arr(int a[],int b[],int c[],int a_size,int b_size,int c_size) {
int small=INT_MAX;
int i,j,k,l;
i=j=k=l=0;
int* p=d;
while(l<a_size+b_size+c_size) {
small=INT_MAX;
if(i!=a_size && a[i]<small)
small=a[i];
if(j!=b_size && b[j]<small)
small=b[j];
if(k!=c_size && c[k]<small)
small=c[k];
if(small==a[i]) i++;
if(small==b[j]) j++;
if(small==c[k]) k++;
d[l++]=small;
}
}
int main() {
int a[]={50,51,52};
int b[]={23,43,76,81};
int c[]={31,55};
int i;
int a_size=sizeof(a)/sizeof(a[0]);
int b_size=sizeof(b)/sizeof(b[0]);
int c_size=sizeof(c)/sizeof(c[0]);
d=(int*)malloc(a_size+b_size+c_size);
merge_arr(a,b,c,a_size,b_size,c_size);
for(i=0;i<(a_size+b_size+c_size);i++)
printf("%d\n",d[i]);
}
The tryParse solution is great. If we still using Int16.Parse, we can similarly modify the code. If the number cannot be parsed an exception will be thrown and caught by the catch block. Otherwise we have successfully parsed the number and we can return true.The code should be:
public static bool ConvertToNumber(string str)
{
try
{
int n = Int16.Parse(str);
}
catch (Exception ex)
{
cout<<"Invalid number\n"<<endl;
}
return true;
I implemented the sort technique in C. I dont think we need to return true or false. The question says, find all pairs which add to the number given. Hence must print out the pairs:
void find_pairs( int a[],int size) {
sort(a);
int first,last,i,j;
first = a[0];
last = a[size-1];
i=0;
j=size-1;
while(j>i) {
if(first+last == num) {
printf("%d,%d\n",first,last);
first=a[++i];
last=a[--j];
}
if(first>num) first= a[++i];
if(last>num) last =a[--j];
}
}
I am not very good at calculating complexity. But this is an O(n) algorithm I guess?
- sowmya.kp May 16, 2015I am new to C++. I came up with this and tested it:
int main() {
map<string,int> no_of_reportees;
map<string,string> reports_to;
map<string,int>::const_iterator j;
map<string,string>::const_iterator i;
reports_to["A"] = "C";
reports_to["B"] = "C";
reports_to["C"] = "F";
reports_to["D"] = "E";
reports_to["E"] = "F";
reports_to["F"] = "F";
for( i = reports_to.begin(); i != reports_to.end() ; ++i ) {
if(i->first != i->second)
{
no_of_reportees[i->second]++;
no_of_reportees[i->second] += no_of_reportees[i->first];
}
}
for(i = reports_to.begin(); i != reports_to.end() ; ++i ) {
cout<< i->first<<":"<<no_of_reportees[i->first]<<"\n";
}
}
Output:
A:0
B:0
C:2
D:0
E:1
F:5
~
I am new to C++. I came up with this and tested it:
int main() {
map<string,int> no_of_reportees;
map<string,string> reports_to;
map<string,int>::const_iterator j;
map<string,string>::const_iterator i;
reports_to["A"] = "C";
reports_to["B"] = "C";
reports_to["C"] = "F";
reports_to["D"] = "E";
reports_to["E"] = "F";
reports_to["F"] = "F";
for( i = reports_to.begin(); i != reports_to.end() ; ++i ) {
if(i->first != i->second)
{
no_of_reportees[i->second]++;
no_of_reportees[i->second] += no_of_reportees[i->first];
}
}
for(i = reports_to.begin(); i != reports_to.end() ; ++i ) {
cout<< i->first<<":"<<no_of_reportees[i->first]<<"\n";
}
}
Output:
A:0
B:0
C:2
D:0
E:1
F:5
~
I took a bit of your idea and came up with this. It works in my test:
int max_marks(int nitems,int max,int marks[],int time[]) {
int i,j,val,k;
for(i=0;i<=nitems;i++)
{
for(j=0;j<=max;j++) {
matrix[i][j] = INT_MAX;
}
}
for(i=1;i<= nitems;i++) {
val=0;
for(k=1;k<= i; k++)
val+= marks[k-1];
for(j=0;j<=max;j++) {
if(j>val) break;
if(marks[i-1] > j)
matrix[i][j]=matrix[i-1][j];
else {
if(matrix[i-1][j-marks[i-1]] == INT_MAX)
matrix[i][j] = time[i-1];
else
matrix[i][j]= min(matrix[i-1][j],time[i-1]+matrix[i-1][j-marks[i-1]]);
}
}
}
return matrix[nitems][max];
}
Say N=10, K=4 i.e I pick 4 balls No. 10,9,8,7. Average is 8.5. Multiplying by 2 gives 17 which is not close to N.
- sowmya.kp May 24, 2015Am I missing something here?