[algogeeks] Range Modulo Problem
You are given a range of modulo operands and find the range of modulo result. Expression :- *x = y % z* where range of y is [ c1, c2 ] c1, c2 are real numbers ( can be +ve or -ve ) and c2 >c1 where range of z is [c3,c4] c3, c4 are real numbers ( can be +ve or -ve ) and c3 >c4 Range of x is [c5,c6] Input: User will input constant numbers( +ve or -ve ) corresponding to c1,c2,c3,c4. Output : c5 and c6. Write an algorithm for it . -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Technology for Graphical User Interface on Linux
Hi all, I am looking for a good tool or language to create graphical user interface in linux environment. Java can be used to achieve the purpose, Can you please let me know any other technology for such purpose. Thanks Sagar -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] C++ initialization list
Hi Saurabh
Thanks for the document. Please refer to start of page 214, Section 8.5.4
,point 3, Below is example from that
struct S2 {
int m1;
double m2, m3;
};
S2 s21 = { 1, 2, 3.0 }; // OK
S2 s22 { 1.0, 2, 3 }; error: narrowing
S2 s23 { }; // OK: default to 0,0,0
I tried the above case with valgrind, even valgrind had not shown any
un-initialized read.
Document also says it is incomplete and incorrect.
Thanks
Sagar
On Sun, Sep 28, 2014 at 4:41 PM, saurabh singh wrote:
> Here you go
> http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2012/n3337.pdf
> The c++ standard itself. Refer to section 8.5.4 page no. 213.
> Looks like even this int a[10] = {2} is not guaranteed to initialize all
> the elements of the array. Sure gcc provides this but then it becomes a
> compiler specific thing. The language doesn't advocates it.
>
> Saurabh Singh
> B.Tech (Computer Science)
> MNNIT
> blog:geekinessthecoolway.blogspot.com
>
> On Sun, Sep 28, 2014 at 3:47 PM, sagar sindwani
> wrote:
>
>> Thanks Deepak and Rahul for the reply.
>>
>> Do you guys have any standard document or any standard book which defines
>> this? I totally agree with these answers but I don't have any formal
>> written text.
>>
>> In my example 1, the object is on stack and this lead to a1[0].z to be
>> un-initialized. But as the specified in example 2, Why every element of arr
>> is initialized, it is also on the stack ? Any source to answer this
>> question ?
>>
>> Thanks
>> Sagar
>>
>>
>>
>> On Sun, Sep 28, 2014 at 2:26 PM, Rahul Vatsa
>> wrote:
>>
>>>
>>> http://stackoverflow.com/questions/3127454/how-do-c-class-members-get-initialized-if-i-dont-do-it-explicitly
>>>
>>> On Sun, Sep 28, 2014 at 12:22 PM, Deepak Garg
>>> wrote:
>>>
>>>> Hi
>>>>
>>>> In example 1, member z will have a garbage value (i.e. 0 in your case )
>>>>
>>>> Thanks
>>>> Deepak
>>>> On Sep 28, 2014 11:29 AM, "sagar sindwani"
>>>> wrote:
>>>>
>>>>> I am working on How compilers handle initialization list. I came
>>>>> across a case where I am not sure what should be the compiler behaviour.
>>>>>
>>>>> *Example 1:-*
>>>>>
>>>>> #include
>>>>>
>>>>> class A
>>>>> {
>>>>> public:
>>>>> int x,y,z;
>>>>> };
>>>>>
>>>>> int main()
>>>>> {
>>>>> A a1[2] =
>>>>> {
>>>>> { 1,2 },
>>>>> { 3,4 }
>>>>> };
>>>>>
>>>>> std::cout << "a1[0].z is " << a1[0].z << std::endl;
>>>>>
>>>>> return 0;
>>>>> }
>>>>>
>>>>> In above case a1[0].z is ? g++ shows it as 0 ( zero ). It is exactly 0
>>>>> or garbage value, I am not sure on that.
>>>>>
>>>>> I tried lot of books and some documents , no where I found what C++
>>>>> says for initialization of class objects.
>>>>>
>>>>> You can find handling of below case in almost every book.
>>>>>
>>>>> *Example 2:- *
>>>>>
>>>>> int arr[6] = {0};
>>>>>
>>>>> In Example 2, compilers will auto-fill all members with 0. It is
>>>>> mentioned in books. But when it comes to User-defined datatypes nothing is
>>>>> mentioned.
>>>>>
>>>>>
>>>>> Please share your thoughts on this. If you find any document related
>>>>> to this, please share it as well.
>>>>>
>>>>> Thanks
>>>>> Sagar
>>>>>
>>>>> --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "Algorithm Geeks" group.
>>>>> To unsubscribe from this group and stop receiving emails from it, send
>>>>> an email to algogeeks+unsubscr...@googlegroups.com.
>>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To unsubscribe from this group and stop receiving emails from it, send
>>>> an email to algogeeks+unsubscr...@googlegroups.com.
>>>>
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an email to algogeeks+unsubscr...@googlegroups.com.
>>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] C++ initialization list
Thanks Deepak and Rahul for the reply.
Do you guys have any standard document or any standard book which defines
this? I totally agree with these answers but I don't have any formal
written text.
In my example 1, the object is on stack and this lead to a1[0].z to be
un-initialized. But as the specified in example 2, Why every element of arr
is initialized, it is also on the stack ? Any source to answer this
question ?
Thanks
Sagar
On Sun, Sep 28, 2014 at 2:26 PM, Rahul Vatsa wrote:
>
> http://stackoverflow.com/questions/3127454/how-do-c-class-members-get-initialized-if-i-dont-do-it-explicitly
>
> On Sun, Sep 28, 2014 at 12:22 PM, Deepak Garg
> wrote:
>
>> Hi
>>
>> In example 1, member z will have a garbage value (i.e. 0 in your case )
>>
>> Thanks
>> Deepak
>> On Sep 28, 2014 11:29 AM, "sagar sindwani"
>> wrote:
>>
>>> I am working on How compilers handle initialization list. I came across
>>> a case where I am not sure what should be the compiler behaviour.
>>>
>>> *Example 1:-*
>>>
>>> #include
>>>
>>> class A
>>> {
>>> public:
>>> int x,y,z;
>>> };
>>>
>>> int main()
>>> {
>>> A a1[2] =
>>> {
>>> { 1,2 },
>>> { 3,4 }
>>> };
>>>
>>> std::cout << "a1[0].z is " << a1[0].z << std::endl;
>>>
>>> return 0;
>>> }
>>>
>>> In above case a1[0].z is ? g++ shows it as 0 ( zero ). It is exactly 0
>>> or garbage value, I am not sure on that.
>>>
>>> I tried lot of books and some documents , no where I found what C++ says
>>> for initialization of class objects.
>>>
>>> You can find handling of below case in almost every book.
>>>
>>> *Example 2:- *
>>>
>>> int arr[6] = {0};
>>>
>>> In Example 2, compilers will auto-fill all members with 0. It is
>>> mentioned in books. But when it comes to User-defined datatypes nothing is
>>> mentioned.
>>>
>>>
>>> Please share your thoughts on this. If you find any document related to
>>> this, please share it as well.
>>>
>>> Thanks
>>> Sagar
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an email to algogeeks+unsubscr...@googlegroups.com.
>>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] C++ initialization list
I am working on How compilers handle initialization list. I came across a
case where I am not sure what should be the compiler behaviour.
*Example 1:-*
#include
class A
{
public:
int x,y,z;
};
int main()
{
A a1[2] =
{
{ 1,2 },
{ 3,4 }
};
std::cout << "a1[0].z is " << a1[0].z << std::endl;
return 0;
}
In above case a1[0].z is ? g++ shows it as 0 ( zero ). It is exactly 0 or
garbage value, I am not sure on that.
I tried lot of books and some documents , no where I found what C++ says
for initialization of class objects.
You can find handling of below case in almost every book.
*Example 2:- *
int arr[6] = {0};
In Example 2, compilers will auto-fill all members with 0. It is mentioned
in books. But when it comes to User-defined datatypes nothing is mentioned.
Please share your thoughts on this. If you find any document related to
this, please share it as well.
Thanks
Sagar
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Why templates are implemented only in Header files
The only portable way of using templates at the moment is to implement them in header files by using inline functions. I copied it from the below link. http://stackoverflow.com/questions/495021/why-can-templates-only-be-implemented-in-the-header-file -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Problem??
B[n]=0;
for i=n to 1
{
if(A[i-1]<=A[i])
B[i-1]=B[i];
else
B[i-1]=B[i]+1;
}
O(n) solution.
Correct me if I am wrong.
On Tue, Oct 4, 2011 at 2:07 PM, anshu mishra wrote:
> int count(int x, int tree[], int s, int e, int n)
> {
> tree[n]++;
> if (s==e) return 0;
> int cnt = 0;
> int mid = (s+e)/2;
> if (mid < x) return tree[2*n+1]+count(x, tree, mid+1, e, 2*n+2);
> else return count(x, tree, s, mid, 2*n+1);
> }
>
> main()
> {
> for(i=n-1;i>=0; i--)
> {
> sol[i] = insert(ar[i], tree, 0, n-1, 0)
>
> }
> }
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Median of 2D matrix
Use K-Median theorem with k=N
On Mon, Nov 7, 2011 at 11:33 PM, Gene wrote:
> Can you explain how a heap helps get the answer? Just to put the
> elements in a heap requires O ( N^2 log (N) ) time.
>
> On Nov 7, 4:12 pm, vikas wrote:
> > I think the best we can have is nlogn solution with the heap approach.
> >
> > On Nov 6, 10:27 pm, Dave wrote:
> >
> >
> >
> > > @Mohit: Here is a counterexample:
> >
> > > 10 1152 53 54
> > > 20 21 112 113 114
> > > 30 31 122 123 124
> > > 40 41 132 133 134
> > > 50 91 142 143 144
> >
> > > The median is 91, and it is not on the anti-diagonal.
> >
> > > Dave
> >
> > > On Nov 6, 3:11 am, mohit verma wrote:
> >
> > > > @Gene
> > > > As i said in my earlier post right to left diagonal partitions the
> martix
> > > > into 2 equal number of elements. So now the median must be in this
> > > > diagonal. Now our focus is on finding median of this diagonal only.
> > > > I think this works fine. Can u give some test case for which it
> fails?
> >
> > > > On Sun, Nov 6, 2011 at 3:02 AM, Gene wrote:
> > > > > Unfortunately this isn't true. See the example I gave earlier:
> >
> > > > > 1 2 3
> > > > > 2 4 5
> > > > > 3 4 6
> >
> > > > > Thje median is 3.
> >
> > > > > 1 2 2 3 >3< 4 4 5 6
> >
> > > > > Niether one of the 3's lies on the diagonal.
> >
> > > > > When you pick any element P on the diagonal, all you know is that
> > > > > anything to the right and downward is no less than P and
> everything to
> > > > > the left and upward is no greater. This leaves the upper right and
> > > > > lower left rectangles of the matrix unrelated to P.
> >
> > > > > On Nov 5, 3:51 am, ankit agarwal
> wrote:
> > > > > > Hi,
> >
> > > > > > I think the median will always lie on the diagonal
> > > > > > a[n][1] a[1][n]
> > > > > > because the elements on the LHS making the upper triangle will
> > > > > > always be less than or equal to the elements on the diagonal
> > > > > > and the RHS, elements in the lower triangle will be greater than
> or
> > > > > > equal to them.
> >
> > > > > > so sort the diagonal and find the middle element, that will be
> the
> > > > > > median.
> >
> > > > > > Thanks
> > > > > > Ankit Agarwal
> >
> > > > > > On Nov 5, 1:29 am, Gene wrote:
> >
> > > > > > > Here's an idea. Say we pick any element P in the 2D array A
> and use
> > > > > > > it to fill in an N element array X as follows.
> >
> > > > > > > j = N;
> > > > > > > for i = 1 to N do
> > > > > > > while A(i, j) > P do
> > > > > > > j = j - 1;
> > > > > > > end;
> > > > > > > X(i) = j;
> > > > > > > end;
> >
> > > > > > > This algorithm needs O(N) time.
> >
> > > > > > > The elements of X split each row with respect to P. That is,
> for each
> > > > > > > i = 1 to N,
> >
> > > > > > > A(i, j) <= P if 0 < j <= X(i),A(i,j) > P if X(i) < j <=
> N.
> >
> > > > > > > Now the strategy is to create two length N arrays a =
> [0,0,...0]; and
> > > > > > > b = [N,N,...]. We'll maintain the invariant that a[i] < Median
> <= b[i]
> > > > > > > for some i. I.e, they "bracket" the median.
> >
> > > > > > > We define functions L(a) = sum_i( a(i) ) and R(b) = sum_i( N -
> > > > > > > b(i) ). These tell us how many elements there are left and
> right of
> > > > > > > the bracket.
> >
> > > > > > > Now reduce the bracket as in binary search: Guess a value P,
> compute
> > > > > > > X. If L(X) >= R(X), set b = X else set a = X.
> >
> > > > > > > Keep guessing new P values in a way that ensures we reduce the
> number
> > > > > > > of elements between a and b by some fixed fraction. If we can
> do
> > > > > > > that, we'll get to 1 element in O(N log N) time.
> >
> > > > > > > The remaining problem is picking good P's. Certainly the first
> time is
> > > > > > > easy. Just take A(N/2, N/2). This has approximately (at least)
> N^2/4
> > > > > > > elements larger than it and N^2/4 smaller due to the sorted
> rows and
> > > > > > > columns. This is what we need to get O(N log N) performance.
> >
> > > > > > > But after the first split, things get trickier. The area
> between a and
> > > > > > > b takes on the shape of a slash / /, so you can't just pick a
> P that
> > > > > > > moves a and b together by a fixed fraction of remaining
> elements.
> >
> > > > > > > Not to worry! You can quickly look up the (at most) N row
> medians in
> > > > > > > the bracket, i.e.
> >
> > > > > > > { A(i, (a[i] + b[i] + 1) / 2) | a[i] >
> > > > > > > and use the well known O(N) median selection algorithm to get
> a median
> > > > > > > of this. This has the quality we want of being somewhere
> roughly in
> > > > > > > the middle half of the remaining elements. The logic is the
> same as
> > > > > > > the selection algorithm itself, but in our case the rows are
> pre-
> > > > > > > sorted.
> >
> > > > > > > In all, each partitioning step requires O(N), and a fixed
> fraction
> > > > > > > (about 1/2) of the elements will
Re: [algogeeks] Re: i cannot solve this written test question
if ( ten's place is != 9)
Decrement the unit place by 1 and increment the ten's place by 1.
else
Increment MSD(Most significant digit) by 1 and decrement next digit by 1.
example:-
712 > 721
897 > 987
On Sun, Oct 9, 2011 at 6:51 PM, wujin chen wrote:
> @Navneet， i mean the length of N is less than 1000, not the value of N .
> *so, N maybe cannot be represented in 32bit . 10^1000-1 is huge number~~
> *
>
> 2011/10/9 Navneet
>
>> sumOfDigits(i) - simply sums all the digits and returns the value.
>> sortDigits() - takes a number and return the lowest possible number
>> possible with digits of param passed.
>> flag = false;
>>
>> for(int i=n+1, i < 1000; i++) //mention to go upto 1000 in problem
>> {
>> if(sumOfDigits(i) == sumOfDigits(n))
>> {
>> //a candidate
>> int sorted i = sortDigits(i);
>> int sorted n = sortDigits(n);
>> if(i == n)
>> {
>> //we found one
>> cout<<"\nDesired number is "<> more
>> flag = true;
>> }
>> }
>> if(!flag)
>> cout<<"\nNo such number found"<> }
>>
>> On Oct 9, 5:04 pm, wujin chen wrote:
>> > @Aamir , yes, for some N, it will be no ans, then return -1.
>> >
>> > 2011/10/9 Aamir Khan
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> > > Answer won't be possible in for each N. What would be answer for
>> N=999 ?
>> >
>> > > On Sun, Oct 9, 2011 at 4:22 PM, Ankur Garg
>> wrote:
>> >
>> > >> Is it sum of bits or sum of digits ?
>> >
>> > >> On Sun, Oct 9, 2011 at 1:39 PM, wujin chen > >wrote:
>> >
>> > >>> Given a positive number N, find a minimum number M greater than N,
>> M has
>> > >>> the same length with N and the sum of the bits are equal.
>> >
>> > >>> example:
>> > >>> N=134 , M=143, // 1+3+4=1+4+3
>> > >>> N=020, M = 101, //2=1+1
>> >
>> > >>> the length of N is less than 1000.
>> >
>> > >>> --
>> > >>> You received this message because you are subscribed to the Google
>> Groups
>> > >>> "Algorithm Geeks" group.
>> > >>> To post to this group, send email to algogeeks@googlegroups.com.
>> > >>> To unsubscribe from this group, send email to
>> > >>> algogeeks+unsubscr...@googlegroups.com.
>> > >>> 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 algogeeks@googlegroups.com.
>> > >> To unsubscribe from this group, send email to
>> > >> algogeeks+unsubscr...@googlegroups.com.
>> > >> For more options, visit this group at
>> > >>http://groups.google.com/group/algogeeks?hl=en.
>> >
>> > > --
>> > > Aamir Khan | 3rd Year | Computer Science & Engineering | IIT Roorkee
>> >
>> > > --
>> > > You received this message because you are subscribed to the Google
>> Groups
>> > > "Algorithm Geeks" group.
>> > > To post to this group, send email to algogeeks@googlegroups.com.
>> > > To unsubscribe from this group, send email to
>> > > algogeeks+unsubscr...@googlegroups.com.
>> > > 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 algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] String
Awesome solution karthik R
On Tue, Sep 13, 2011 at 3:02 PM, kARTHIK R wrote:
> Something like this.
>
>
> stack S;
> void function(char *s) {
>char *ptr=s;
>while(*ptr++ !=' ') {}
>*ptr = '\0';
> S.push(s); // Will push the string till NULL into
> the stack
> function(ptr+1);
> }
>
>
> // Pop from stack to get words
>
> Karthik R
>
>
>
> On Tue, Sep 13, 2011 at 2:50 PM, guna sekaran wrote:
>
>> please write a code any one
>>
>> On Tue, Sep 13, 2011 at 2:06 PM, shady wrote:
>> > search archives, already done
>> >
>> > On Tue, Sep 13, 2011 at 1:39 PM, Anshul Khandelwal
>> > wrote:
>> >>
>> >> U can take command line argument in main
>> >> main(int argc,char * argv[ ])
>> >> { for(i=argc-1,i>=0;i--) printf("%s ",argv[i]);
>> >> }
>> >>
>> >>
>> >> On Tue, Sep 13, 2011 at 12:05 AM, hary rathor
>> >> wrote:
>> >>>
>> >>> kapil : in your solution you are required extra O(n+n*sizeOf(int *))
>> both
>> >>> memory to create a link list that really costly
>> >>>
>> >>>
>> >>> --
>> >>> You received this message because you are subscribed to the Google
>> Groups
>> >>> "Algorithm Geeks" group.
>> >>> To post to this group, send email to algogeeks@googlegroups.com.
>> >>> To unsubscribe from this group, send email to
>> >>> algogeeks+unsubscr...@googlegroups.com.
>> >>> For more options, visit this group at
>> >>> http://groups.google.com/group/algogeeks?hl=en.
>> >>
>> >>
>> >>
>> >> --
>> >> Regards
>> >> ANSHUL KHANDELWAL
>> >> Final year
>> >> Computer Engineering
>> >> NIT Jaipur
>> >>
>> >>
>> >> --
>> >> You received this message because you are subscribed to the Google
>> Groups
>> >> "Algorithm Geeks" group.
>> >> To post to this group, send email to algogeeks@googlegroups.com.
>> >> To unsubscribe from this group, send email to
>> >> algogeeks+unsubscr...@googlegroups.com.
>> >> 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 algogeeks@googlegroups.com.
>> > To unsubscribe from this group, send email to
>> > algogeeks+unsubscr...@googlegroups.com.
>> > 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 algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: unique no. problem
http://stackoverflow.com/questions/3963409/interview-question-dealing-with-m-occurrences-among-n On Tue, Sep 13, 2011 at 1:48 PM, Gene wrote: > Here's a way: > > The base 2 xor operator has an obvious extension to base 3 such that > for all integers N, N ^ N ^ N = 0, just like the normal xor has N ^ > N = 0. > > This base 3 operator a^b just adds corresponding digit pairs of a and > b mod 3 to get the digits of the result. > > So the algorithm is to convert each input number to base 3 and tally > up the total with the base 3 ^ operator. The result will be the > answer in base 3. > > The example above in base 3 is > 2,1,11,12,1,11,2,2,11,1 > > Running total with ^: > > 0 ^ 2 = 2 > 2 ^ 1 = 0 > 0 ^ 11 = 11 > 11 ^ 12 = 20 > 20 ^ 1 = 21 > 21 ^ 11 = 2 > 2 ^ 2 = 1 > 1 ^ 2 = 0 > 0 ^ 11 = 11 > 11 ^ 1 = 12 > > And 12 is 5 base 3. > > The total will never have more digits than the biggest number. This > is O(1) space. You have to assume base 3 conversion is a constant > time operation, but this is pretty reasonable. > > If the problem changes to "all the numbers are repeated K times except > for one, which appears only once, you can do the same thing with base > K to get the answer. > > On Sep 11, 2:10 pm, Neha Singh wrote: > > You are given an array that contains integers. The integers content is > such > > that every integer occurs 3 times in that array leaving one integer that > > appears only once. > > Fastest way to find that single integer > > eg: > > Input: [2,1,4,5,1,4,2,2,4,1] > > Answer: 5 > > > > The solution must be of O(n) time and O(1) space > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
