Hemanth Muttevi
BAN USERTested with 99100101102104
and 12345678911
#include<iostream>
#include<stdio.h>
//#include<math.h>
#include<stdlib.h>
using namespace std;
int counter =0;
int missingNUM=0;
int digitChangeHappened=0;
const char* input="12345678911";
bool checkmissing(int* ,int);
int inline pow(int x,int y)
{
int i;
int ret=1;
for(i=0;i<y;i++)
{
ret *= x;
}
return ret;
}
int main()
{
// int counter =0;
int n=20;
int a[n];
// copying the string
while(*input)
{
//cout<<"the element is :"<<(*input)<<"\t";
a[counter]=(*input)-48;
counter++;
input++;
}
for(int h=0;h<14;h++)
{
cout<<a[h]<<endl;
}
input=input-counter;
cout<<"the starting num is :"<<(*input)<<endl;
for(int j=2; j<counter; j++)
{
int lhs=0;
int rhs=0;
int numChange=1;
int maxNumInNthDigit=0;
if(numChange)
{
if(digitChangeHappened)
{
j--;
}
for(int m=0;m<j;m++)
{
int plhs= j-m;
maxNumInNthDigit=maxNumInNthDigit+9*pow(10,plhs-1);
}
numChange=0;
}
//find hte lhs
for(int k=0; k<j; k++)
{
lhs=lhs+(a[k])*pow(10,j-k-1);
}
if(lhs==maxNumInNthDigit)
{
numChange=1;
digitChangeHappened=1;
++j;
}
for(int k=0; k<j; k++)
{
int powerOften= (j-(k+1));
volatile int powerValue=pow(10,j-k-1);
// cout<<"j="<<j<<"\t k="<<k<<"\t powe="<<powerValue<<endl;
int arraynum=a[k+j-numChange];
rhs=rhs+(powerValue)*(arraynum);
}
if((lhs==(rhs-1))||(lhs==(rhs-2)))
{
bool b=checkmissing( a , (j-digitChangeHappened) );
if(!b)
{
continue;
}
else
{
exit(0);
}
}
else
{
digitChangeHappened=0;
continue;
}
}
cout<<"there is no mising number"<<endl;
}
bool checkmissing(int a[] ,int j)
{
int numChange=1;
int maxNumInNthDigit=0;
// int a[counter];
for(int q=0;q<counter-1;q=q+j-numChange)
{
int lhs=0;
int rhs=0;
if(numChange)
{
//j--;
for(int m=0;m<j;m++)
{
maxNumInNthDigit=maxNumInNthDigit+9*pow(10,j-m-1);
}
numChange=0;
}
//find hte lhs
for(int k=0; k<j; k++)
{
lhs=lhs+(a[q+k])*pow(10,j-k-1);
}
if(lhs==maxNumInNthDigit)
{
numChange=1;
++j;
}
for(int k=0; k<j; k++)
{
rhs=rhs+(a[q+k+j-numChange])*pow(10,j-k-1);
}
if((lhs==(rhs-1)))
{
continue;
}
else if((lhs==(rhs-2)))
{
if(missingNUM)
{
cout<<"mutlple missings so returning "<<endl;
return false;
}
missingNUM=lhs+1;
continue;
}
else if(q==counter-j)
{
if(!missingNUM)
{
cout<<"No Missing number found";
return false;
}
else
{
cout<<"Misisng number is :"<<missingNUM<<"\n";
return true;
}
}
else
{
return false;
}
}
}
see let the sum 8 be maximum weight ....
and our denomination to make such a sum be 1,2,3,4,5,6,7,....... k where k<sum here k is less than 8 so k=7.
now print all the maximum possible sets of find sum 8 from giving denominations...
u can do this problem with dynamic programming also.....
see following link so that you will get an idea ..."ww.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Greedy/greedyIntro."
see above is nothing but a different form of knapsack problem which sum to particular weight.. here total weight is 8 and values are natural numbers.... search google for fractional knapsack problem .. Now the algo is everywhere all you need to do is code in your known language....
Hemanthed
see above is nothing but a different form of knapsack problem which sum to particular weight.. here total weight is 8 and values are natural numbers.... search google for fractional knapsack problem .. Now the algo is everywhere all you need to do is code in your known language....
Hemanthed
there could be a problem :
- Hemanth Muttevi September 06, 2013suppose f=53.64
when i write code :
j is index after decimal part
while(rational>0)
{
int integer=(int)rational;
rational=rational-integer;
strin[j]=48+integer;
cout<<"thave value in decimal "<<j<<" is"<<strin[j]<<endl;
j++;
rational=rational*10;
}
i expect sollution to be 53.64
but actual result is :53.639999.....( where ... are digits till end of array) .
Now the question is how to round off 53.63999 to 53.64.. (Even the interview wants this too i guess, which is how float is represented in language )