Vaibhav, Hmm, fine that. I am more interested in the 2nd approach. The first approach is simple brute force.
On Sat, Aug 6, 2011 at 3:11 PM, <[email protected]> wrote: > Mukul, in first approach instead of sending the string again and again u > can use the formula > (a*b)%m = ((a%m)*(b%m))%m > this way u can do sumthin like dis > > int count = 0, a = 1; > while(a != 0) { > count++; > a = ((a*10)%n + 1) %n; > } > > n later output a string consisting of count one's.. > > Regards > VM > > 3rd Year, Computer Engineering, > Netaji Subhas Institute of Technology. > > On , Mukul Gupta <[email protected]> wrote: > > Manee, Nice Question. > > I have thought of two algorithms. I wanted to know how one judges them. > Both have similar time complexity but the 2nd one is slightly complex and > much more logical. > > > > 1. Keeping on adding 1 as a string of 1's and apply it to this modulo > function to check when it becomes 0. > > > > > > long long modulo(char b[],long long a) > > {long long d=0,len,i,j,k; > > len=strlen(b); > > for (k=0;k {d*=10; > > > d+=b[k]-48; > > d=d%a; > > } > > > > return d; > > > > } > > > > > > 2. Any number ending in 3 will have the last digit as 1 if it is > multiplied by 7. > > Consider a case 13 ...let the required answer have 11.....111. as its > representation.....13 x 7 = 91..... > > So subtracting the 3 digit of of 111..1111 by 91...we get > 111...11020....Now we know that the ones digit of the required number is > 7... > > > > Similarly, if the last digit of a ten's digit has to be '2'...The > number has to be multiplied by 4.....So we subtract 13 x 4 = 52 from..... > > 11111.111102 to get 11...050...So we get the ten's digit as 4.... > > > > Similarly, now for a number to end in 5...it has to be multiplied by > 5....we subtract...65 from 111...105....to get 111..1040... > > Hundred's digit is 5 > > Similarly, now for a number to end in 4...it has to be multiplied by > 8 ... we subtract 104 from 111...104....to get 111...000. and thus we end > the process as we have got the remainder as 0. > > > > Thus, our required answer is 13 x 8547 = 111111 > > > > Now I want to know...that both the methods have similar complexity ie. > O(k) where k is the number of 1's. However, 2nd is much more logical and > complex. What does the company look for? > > > > Suggest some better methods or make ammends. > > > > Regards, > > > > Mukul Gupta > > 3rd Year, Computer Engineering, > > Netaji Subhas Institute of Technology. > > > > > > > > > > > > > > > > > > > > On Sat, Aug 6, 2011 at 9:51 AM, sahil gujral [email protected]> > wrote: > > > > yes u r wrong..111111111 is nt divisible by 23 > > > > > > On Sat, Aug 6, 2011 at 9:15 AM, sumit [email protected]> wrote: > > > > > > This looks quite simple. > > > > Every number ending in 3 follows a pattern.eg- > > > > 3 - 111 > > > > 13 - 111111 > > > > 23 - 111111111 etc > > > > we can find the reauired no. by : > > > > suppose input no. is 33 > > > > In every case leave the no at 1's place(least significant) i.e. 3, In > > > > 33 you will be left with 3(after removal of 3 at first place). > > > > Now ,3 *(rest of nos +1 ) is your answer (in case of 33 it is 3*(3+1) > > > > = 12 i.e 111111111111). > > > > for 103 it is 3*(10+1) = 33 1's. > > > > > > > > Correct if I am wrong. > > > > > > > > > > > > > > On Aug 5, 4:33 pm, Manee [email protected]> wrote: > > > > > ADOBE asks the very basic C/C++ questions > > > > > > > > > > one of their toughest however was : > > > > > > > > > > every number ending in 3 has a multiple of the form "111...111" > > > > > > > > > > e.g 3 has 111 > > > > > 13 has 111111 > > > > > so on.. > > > > > > > > > > find the algo for finding the number for an input number ending in 3. > > > > > > > > > > On Aug 5, 2:33 pm, Agyat [email protected]> wrote: > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > hey, guys adobe is visiting our campus. So those who know questions > > > > > > that adobe asked in written or interview, please post here as it will > > > > > > be of great help (as adobe has visited some colleges already). > > > > > > Thank you in advance. > > > > > > > > -- > > > > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > > > > To post to this group, send email to [email protected]. > > > > To unsubscribe from this group, send email to > [email protected]. > > > > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > -- > > > > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > > > > To post to this group, send email to [email protected]. > > > > To unsubscribe from this group, send email to > [email protected]. > > > > > > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > > > > > > > > > > > > > > > > > > > > > > > > > -- > > > > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > > > > To post to this group, send email to [email protected]. > > > > To unsubscribe from this group, send email to > [email protected]. > > > > > > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > > > > > > > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
