help in improving algo ...

[joshilay]

given a positive integer n ,we have to find the number of possible combination of integers (i,j) where i+j=k ... given 0<=i,j,k<=n
i code this problem as below ...

#include<iostream.h>
#include<conio.h>
void max(int n,int x,int k,int *no)
{
 if(x>=0)
  {
  max(n,x-1,k,no);
  if(n+x==k)
   {
    (*no)+=1;
    cout<<"\n"<<" The combinations are formed by "<<n<<" "<<x;
   }
 return;
}
 
if(n>=0)
 max(n-1,n-1,k,no);
return;
}
 
 
void main()
{
clrscr();
int x,k,n,*no;
no=new int();
*no=0;
cout<<"enter k :";
cin>>k;
cout<<"\n enter n : ";
cin>>n;
max(n,n,k,no);
cout<<"\nTotal number is : "<<*no;
getch();
}

can anyone help in improving the time complexity of this problem ???

[Dave Sinkula]

Might I first ask why you are using nonstandard headers and code? It seems to me that learning the basics of the language precede optimization issues. Why is "time complexity" an issue?

Don't use void main. Why dynamically allocate a single int? Use good indenting and meaningful variable names. In short, coax my interest in your problem by showing me your efforts. And post code using code tags from here on out.

[joshilay]

Might I first ask why you are using nonstandard headers and code? It seems to me that learning the basics of the language precede optimization issues. Why is "time complexity" an issue?

Don't use void main. Why dynamically allocate a single int? Use good indenting and meaningful variable names. In short, coax my interest in your problem by showing me your efforts. And post code using code tags from here on out.

thanks for that ..i am just a starter ..so there could be some mistakes there !!!

[Dave Sinkula]

My first stab might be some of the "conditioning" I mentioned.

#include <iostream>
using std::cout;
using std::cin;

void max(int n, int x, int k, int *total)
{
   if ( x >= 0 )
   {
      max(n, x - 1, k, total);
      if ( n + x == k )
      {
         *total += 1;
         cout << "The combinations are formed by " << n << ' ' << x << '\n';
      }
   }
   else if ( n >= 0 )
   {
      max(n - 1, n - 1, k, total);
   }
}


int main()
{
   int k, n, total = 0;

   cout << "enter k : ";
   cin  >> k;
   
   cout << "enter n : ";
   cin  >> n;
   
   max(n, n, k, &total);
   cout << "Total number is : " << total << '\n';
   
   cin.get(); // discard leftover newline
   cin.get(); // wait for [enter]
   
   return 0;
}

I've done nothing much else with it. Do you find it easier to read and follow?

[joshilay]

My first stab might be some of the "conditioning" I mentioned.

#include <iostream>
using std::cout;
using std::cin;
 
void max(int n, int x, int k, int *total)
{
   if ( x >= 0 )
   {
      max(n, x - 1, k, total);
      if ( n + x == k )
      {
         *total += 1;
         cout << "The combinations are formed by " << n << ' ' << x << '\n';
      }
   }
   else if ( n >= 0 )
   {
      max(n - 1, n - 1, k, total);
   }
}
 
 
int main()
{
   int k, n, total = 0;
 
   cout << "enter k : ";
   cin  >> k;
 
   cout << "enter n : ";
   cin  >> n;
 
   max(n, n, k, &total);
   cout << "Total number is : " << total << '\n';
 
   cin.get(); // discard leftover newline
   cin.get(); // wait for [enter]
 
   return 0;
}

I've done nothing much else with it. Do you find it easier to read and follow?

thanks for that ..defianately i will learn from that ..ya its much easier to read ...but can u still me a better algorithm than this