mukul, pls explain my following doubts: 1. whats the need of subtracting the numbers, like u subtracted 91 then 52 etc... 2. the ones digit 7 is ok... didnt get how did u reach 4??
On Sat, Aug 6, 2011 at 3:22 PM, Mukul Gupta <[email protected]>wrote: > 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. > -- 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.
