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 ur 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) ie 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 ie 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"
>
> eg 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.
