Re: [algogeeks] Re: increment operator...

[Aamir Khan]

@vishwa : that is not correct. Check : http://ideone.com/Kn7hRn


On Wed, Nov 7, 2012 at 9:20 PM, vishwa  wrote:

> I guess its other way.
>
> According you guys explanation after evaluating the expression first the
> if condition turns out to be   if(1);
>
> And the program runs infinitely..
>
> first  --   ++k <= 8   ---   turns true and k becomes  6.
>
> second -- k++ / 5   ---   skipped. k remains  6
>
> third -- ++k < 5  ---   turns false and k becomes 7.
>
>
> Hope its very clear
>
>
>
>
> On Wed, Nov 7, 2012 at 7:13 AM, apsalar  wrote:
>
>> We start with k = 5.
>>
>> if ++k < 5 translates to if 6 < 5 => which is false.
>> No need to evaluate k++/5 (short-circuiting)
>> if ++k <= 8 translates to (6+1) 7 <= 8 which is true.
>> So, 7 gets printed.
>>
>>
>> On Tuesday, November 6, 2012 6:22:13 AM UTC-5, Anil Sharma wrote:
>>>
>>> main()
>>>  {
>>>   int k = 5;
>>>   if (++k < 5 && k++/5 || ++k <= 8);
>>>   printf("%d ", k);
>>>  }
>>>
>>> the output shud be 8 but it comes out to be 7.why???
>>> as increment operator has higher precedence among them so increment shud
>>> be done throughout at first and after then other operators shud be
>>> evaluated.sooutput shud be 8.
>>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/KgsSjel6n_4J.
>>
>> 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.
>>
>
>
>
> --
> *Thanks & Regards,*
> *Vishwa*
> *+91 9964051504*
>
>  --
> 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 | 4th 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.

[algogeeks] increment operator...

[Aamir Khan]

Let's concentrate on if condition,

*if (++k < 5 && k++/5 || ++k <= 8);*

is equivalent to (based on operator precedence)

*if (((++k < 5) && (k++/5)) || (++k <= 8));*

Initially k = 5.

Step1 : The first term in if clause i.e, (++k < 5) is false which makes the
*((++k < 5) && (k++/5)) *false because all the variables in && should be 1.

this makes k = 6 because of execution of (++k < 5).

Step 2 : Now if condition is equivalent to if(0 || (++k <= 8))

it will check the second condition, (++k <= 8) thereby incrementing k by 1
and returns 1 (making if condition true though it's not relevant for this
problem)

Hence, k = 7 after execution of this program.



On Tuesday, November 6, 2012, Anil Sharma wrote:

> main()
>  {
>   int k = 5;
>   if (++k < 5 && k++/5 || ++k <= 8);
>   printf("%d ", k);
>  }
>
> the output shud be 8 but it comes out to be 7.why???
> as increment operator has higher precedence among them so increment shud
> be done throughout at first and after then other operators shud be
> evaluated.sooutput shud be 8.
>
> --
> 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 | 4th 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.

[algogeeks] Re: Printing all inversions in an array

[Aamir Khan]

On Monday, October 22, 2012, Dipit Grover wrote:

> Since the number of inversions are of order n^2 in the worst case, so
> should be the complexity of printing them apparently.


It makes sense to some extent but this is no proof. There has to be a
better proof for lower bound of complexity for this algorithm. Because I
can state similar statement,

"Since the number of inversions are of order N^2 in the worst case, so
should be the complexity of counting them apparently".

But we all know this is not true as we already know O(nlogn) solution.


>  --
> 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 'algogeeks@googlegroups.com');>
> .
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com  'algogeeks%2bunsubscr...@googlegroups.com');>.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>


-- 

Aamir Khan | 4th 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.

[algogeeks] Printing all inversions in an array

[Aamir Khan]

What is the best algorithm to print all the inversions in an array? While
you can find the inversion count using modified merge sort procedure in
O(nlog(n)) time [1] but I doubt that printing all inversions can also be
done in O(nlogn).

In an array A[], two elements A[i] and A[j] form an inversion if A[i] >
A[j] and i < j

[1] http://www.geeksforgeeks.org/archives/3968


-- 

Aamir Khan | 4th 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.

Re: [algogeeks] A theoritical question

[Aamir Khan]

On Mon, Dec 5, 2011 at 4:33 PM, saurabh singh  wrote:

> I said *uncountably infinite.* *Integers are countably infinite.* *A
> countably infinite set will require finite number of states as we can
> arrange them in order.*

What about addition of real numbers then. Real numbers are uncountably
infinite.

>
>
> On Mon, Dec 5, 2011 at 4:26 PM, Aamir Khan  wrote:
>
>>
>>
>> On Mon, Dec 5, 2011 at 3:31 PM, saurabh singh wrote:
>>
>>> I was wondering can we design a machine(Even hypothetical)  that can
>>> find a *perfect square root *of any integer thats given to it.
>>> My logic why we can't is since there are uncountably infinite real
>>> numbers, there will be uncountably infinite numbers requiring infinite
>>> states on a turing machine.But since there are only finite number of
>>> states,we cant make such a machine.And since we cant make a turing machine
>>> for calculating the square root we cant make any computing machine for the
>>> same.
>>> I am not sure about my logic though.Thats why i have this doubt.
>>>
>>> Just a thought, If you are saying that there are infinite real numbers
>> then it will require infinite number of states on turing machine. So, the
>> same explanation holds for every arithmetic operation. If you talk about
>> addition then also there are infinite number of numbers so there must be
>> infinite number of states and so not possible to have such a machine
>> according to your argument but we do have such machines.
>>
>> My point is that you are wrong somewhere that since there are infinite
>> real numbers so we must have infinite number of states in turing machine.
>>
>> --
>>> Saurabh Singh
>>> B.Tech (Computer Science)
>>> MNNIT ALLAHABAD
>>>
>>>
>>>  --
>>> 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.
>>
>
>
>
> --
> Saurabh Singh
> B.Tech (Computer Science)
> MNNIT ALLAHABAD
>
>
>  --
> 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.

Re: [algogeeks] A theoritical question

[Aamir Khan]

On Mon, Dec 5, 2011 at 3:31 PM, saurabh singh  wrote:

> I was wondering can we design a machine(Even hypothetical)  that can find
> a *perfect square root *of any integer thats given to it.
> My logic why we can't is since there are uncountably infinite real
> numbers, there will be uncountably infinite numbers requiring infinite
> states on a turing machine.But since there are only finite number of
> states,we cant make such a machine.And since we cant make a turing machine
> for calculating the square root we cant make any computing machine for the
> same.
> I am not sure about my logic though.Thats why i have this doubt.
>
> Just a thought, If you are saying that there are infinite real numbers
then it will require infinite number of states on turing machine. So, the
same explanation holds for every arithmetic operation. If you talk about
addition then also there are infinite number of numbers so there must be
infinite number of states and so not possible to have such a machine
according to your argument but we do have such machines.

My point is that you are wrong somewhere that since there are infinite real
numbers so we must have infinite number of states in turing machine.

-- 
> Saurabh Singh
> B.Tech (Computer Science)
> MNNIT ALLAHABAD
>
>
>  --
> 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.

Re: [algogeeks] NUMBER OF MST ?

[Aamir Khan]

On Sun, Dec 4, 2011 at 12:10 AM, praveen raj  wrote:

> N!/2
>
N!/2 is definitely wrong as you guys are thinking of MST with just two
terminal nodes. All the MSTs will be much more than N!/2 because of any
number of terminal nodes possible, but i can't find the closed form it.

>
> On 03-Dec-2011 11:30 PM, "Dipit Grover"  wrote:
> >
> > ^ we need to count "each permutation and its reverse" together as one
> possibility since both would result in identical mst.
> >
>



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.

Re: [algogeeks] facebook interview question

[Aamir Khan]

Take numbers in pair of 2, compare with each other and then compare the
maximum among them with max (maximum element so far) and minimum among them
with min (minimum element so far) , In this way you will be able to find
max, min in 3 comparisons for each 2 integers. Hence 3n/2 comparisons
needed for finding min and max simultaneously in an array.


On Mon, Nov 28, 2011 at 9:56 PM, Nitin Garg wrote:

> Find the min and max in an array. Now do it in less than 2n comparisons.
> (they were looking for the solution that finds both max and min in about
> 3/2 n comparisons).
>
>
> --
> Nitin Garg
>
> "Personality can open doors, but only Character can keep them open"
>
> --
> 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.

Re: [algogeeks] An Array Problem

[Aamir Khan]

On Tue, Nov 22, 2011 at 11:50 PM, tech coder wrote:

> here is an O(n) approach  using  a stack.
>
> problem can be stated as " find the 1st smaller element on the right.
>
> put the first element in stack.
> take next element suppose "num"  if this number is less than elements
>  stored in stack, pop those elements , for these pooped elements  num will
> be the required number.
> put the the element (num)   in stack.
>
> repeat this.
>
> at last the elements which are in next , they will have 0 (valaue)
>
> @techcoder : If the numbers are not in sorted order, What benefit the
stack would provide ? So, are you storing the numbers in sorted order
inside the stack ?

I can think of this solution :

Maintain a stack in which the elements will be stored in sorted order. Get
a new element from array and lets call this number as m. Push m into the
stack. Now, find all elements which are <= (m-1) using binary search. Pop
out all these elements and assign the value m in the output array. Elements
remaining at the end will have the value 0.

I am not sure about the complexity of this algorithm...


> On Wed, Nov 23, 2011 at 12:02 AM, Anup Ghatage  wrote:
>
>> I can't think of a better than O(n^2) solution for this..
>> Any one got anything better?
>>
>>
>>
>> On Tue, Nov 22, 2011 at 8:23 PM, Ankuj Gupta  wrote:
>>
>>> Input: A unsorted array of size n.
>>> Output: An array of size n.
>>>
>>> Relationship:
>>>
>>> > elements of input array and output array have 1:1 correspondence.
>>> > output[i] is equal to the input[j] (j>i) which is smaller than
>>> input[i] and jth is nearest to ith ( i.e. first element which is smaller).
>>> > If no such element exists for Input[i] then output[i]=0.
>>>
>>> Eg.
>>> Input: 1 5 7 6 3 16 29 2 7
>>> Output: 0 3 6 3 2 2 2 0 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.
>>>
>>>
>>
>>
>> --
>> Anup Ghatage
>>
>>  --
>> 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*
> *"The Coder"*
>
> *"Life is a Game. The more u play, the more u win, the more u win , the
> more successfully u play"*
>
>  --
> 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.

Re: [algogeeks] Re: finding closest points

[Aamir Khan]

On Tue, Nov 22, 2011 at 8:43 PM, Dave  wrote:

> @Ganesha: You could use a max-heap of size k in time O(n log k), which
> is less than O(n log n) if k < O(n).


We can always ensure that k <= n/2.

If k >= n/2 then the problem can be stated as, find m points farthest from
the given point by creating min-heap of size m. The elements which were
present in input but not in heap will be the points nearest to the given
point, where m = n-k.




> Dave
>
> On Nov 22, 8:56 am, ganesha  wrote:
> > Given a set of points in 2D space, how to find the k closest points
> > for a given point, in time better than nlgn.
>
>

-- 
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.

[algogeeks] Long nCr Calculations

[Aamir Khan]

Lets say i want to calculate (1000C500)%MOD.

*My Code : *
*
*
long long ans=n;
for(int i=1;i<=r;i++) {
ans=(ans*(n-i+1))/i;
ans = ans%MOD;
}


But when the ans inside the loop starts exceeding MOD and you take
ans=ans%MOD then you cannot be sure to get the correct answer..


How to deal with this situation ?


-- 
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.

Re: [algogeeks] What Data Structure to use ?

[Aamir Khan]

>
>
> On Sun, Oct 30, 2011 at 1:17 AM, Aamir Khan  wrote:
>
>> In a university, students can enroll in different courses. A student may
>> enroll for more than one course. Both students and courses can be
>> identified by IDs given to them. Design a data structure to store
>> students, courses, and the student-course relationships. You can use
>> arrays, lists, stacks, trees, graphs, etc. or come up with your own data
>> structures. Give the running times, in Big O notation, for the following
>> operations for your data structure and justify the answers:
>>
>> a) Return all students in a list.
>> b) Return all courses in a list.
>> c) Return all courses in a list for a given student.
>> d) Return all students in a list for a given course.
>>
>>
>> Lets bring a little bit complication,

What if a students wants to know list of all people who share maximum
number of courses with him/her ?

Naive approach : First getting all the courses from the hash tables and
then for each course traversing its list of students, for each student
encountered in this way we can just increase the count. Then all the people
having maximum count and print them.

Any better approach ?

>
>>
>>
>> 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.
>>
>
>


-- 
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.

[algogeeks] What Data Structure to use ?

[Aamir Khan]

In a university, students can enroll in different courses. A student may
enroll for more than one course. Both students and courses can be identified
by IDs given to them. Design a data structure to store students, courses,
and the student-course relationships. You can use arrays, lists, stacks,
trees, graphs, etc. or come up with your own data structures. Give the
running times, in Big O notation, for the following operations for your data
structure and justify the answers:

a) Return all students in a list.
b) Return all courses in a list.
c) Return all courses in a list for a given student.
d) Return all students in a list for a given course.





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.

Re: [algogeeks] [SPOJ] ZSUM

[Aamir Khan]

As far as modular arithmetic is concerned,

(x * z *z )%MOD = (x *(z *z)%MOD)%MOD = ((x%MOD)*(z%MOD)*(z%MOD))%MOD

But when you try to calculate *(x * z * z)%MOD*, the intermediate result of* (x
* z * z) *overflows the integer limit and hence gives the wrong result.

similarly, intermediate value of *(x%MOD) * (y%MOD) * (z%MOD)* might also
overflow the integer limit hence you are getting WA.

On Tuesday, October 25, 2011, Kunal Patil wrote:

> Can you tell why (x * z * z) % MOD is different from (x * ( (z*z)%MOD) ) %
> MOD
>
> Again why ((x%MOD)*(z%MOD)*(z%MOD))%MOD is giving WA 
>
> I thought of a simple examples like
> (100* 53*72) % 90
>   --> ((90+10)*53*72) % 90
>   --> (10*53*72)% 90   which is same as (100%90 * 53%90 * 72%90) % 90
>
> Another example
> (100*91*92)%90
>--> ( (90+10)*(90+1)*(90+2) ) % 90
>--> 10 * 1 * 2 which is again same as (100%90 * 91%90 * 92%90) % 90
>
> Are results different because of range overflow in case of bigger z ???
>
> I'm weak at modular mathematics [?] So please help !!
>
>
> On Thu, Oct 20, 2011 at 11:48 AM, Wasif Hossain <
> wasifhossain@gmail.com> wrote:
>
>> Just a MINOR change.
>> please change the RED line(I've marked it below) in your code by the
>> following line:
>> *return (x*((z*z)%MOD))%MOD;*
>> and enjoy an *ACCEPTED *verdict.*
>> *
>>
>> *Wasif Hossain**
>> *
>> B.Sc. Student of Final Semester,
>> Computer Science and Engineering(CSE),
>> Bangladesh University of Engineering and Technology(BUET),
>> Dhaka-1000
>> Bangladesh.
>>
>> On Thu, Oct 6, 2011 at 1:13 AM, hashd  wrote:
>>
>>> I'm getting WA on the question : 
>>> ZSUM-SPOJ
>>>
>>> Here is my code: 
>>>
>>>
>>> #include
>>> #define MOD 1007
>>>
>>> typedef unsigned long long u64;
>>> using namespace std;
>>>
>>> u64 modExp(u64 x, u64 y){
>>> if(x==0)
>>> return 0;
>>>
>>> if(y==0)
>>> return 1;
>>>
>>> u64 z = modExp(x,y/2);
>>>
>>> if(y%2==0)
>>> return (z*z)%MOD;
>>> else
>>> *return (x*z*z)%MOD;*
>>> }
>>>
>>> int main(){
>>> u64 n, k; scanf("%llu%llu",&n,&k);
>>> while(n&&k){
>>> u64 ans = 0;
>>>
>>> if(n>0)
>>> ans = (2*modExp(n-1,k) + modExp(n,k) + 2*modExp(n-1,n-1) +
>>> modExp(n,n))%MOD;
>>>
>>> printf("%llu\n",ans);
>>> scanf("%llu%llu",&n,&k);
>>> }
>>>
>>> return 0;
>>> }
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To view this discussion on the web visit
>>> https://groups.google.com/d/msg/algogeeks/-/p6j7nmaEUb4J.
>>> 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.

<<33D.gif>>

Re: [algogeeks] Re: Modular arithmetic

[Aamir Khan]

On Sat, Oct 22, 2011 at 9:04 PM, Mad Coder  wrote:

>
>
> Can anyone explain why ((n%p)*(m%p))%p will give wrong answer ?
>
> Lets say, n = 10^15 , m = 10^15   and p = 10^18

So,
n%p = 10^15
m%p = 10^15

And the intermediate result (n%p)*(m%p) will overflow the long long range.

>  --
> 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.

[algogeeks] Modular arithmetic

[Aamir Khan]

Lets say n,m and p are three long long integers.

i want to calculate (n*m)%p.

If (n*m) overflows the limit of long long then the answer would be wrong.
Moreover if i do ((n%p)*(m%p))%p then also there is no certainty of getting
correct answer.

How should i do this in C++ ?

-- 
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.

Re: [algogeeks] i cannot solve this written test question

[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.

[algogeeks] MULTQ3 Run Time Error

[Aamir Khan]

I am getting Run Time Error in MULTQ3 .
I have implemented the segment tree and i can't understand why i can get the
run time error in spoj judge. I tried to generate random input values and
they ran fine on my system.

If i try to increase the MAX value then TLE starts to appear. Since value of
N<=10 so MAX 50 is more than enough to accommodate all nodes in
segment tree.


#include
#include
#include
using namespace std;

#define MAX 50

int M1[2*MAX+1];
int M2[2*MAX+1];
int flag[2*MAX+1];


void Refresh(int node,int begin,int end) {
 int temp = M2[node];
  M2[node] = M1[node];
 M1[node] = (end - begin) + 1 - M1[node] - temp;
flag[node]--;
 flag[node*2] = (flag[2*node]+1)%3;
flag[2*node+1] = (flag[2*node+1]+1)%3;
}

int query(int node, int b, int e, int i, int j) {
 if(b>j || e0) {
 Refresh(node, b, e);
}
 if(b==i && e==j) {
 return (e-b+1 - M1[node]-M2[node]);
}
 int mid = (b+e)>>1;

 return query(2*node, b, mid, max(i, b), min(j,e)) + query(2*node+1, mid+1,
e, max(mid+1,i) ,min(e,j) );

}


void update(int node, int b, int e,int i, int j) {
if(i > e || j0) {
 Refresh(node, b, e);
}


if( b>=i && e<=j) {
 if(flag[node]==0) {
Refresh(node, b, e);
 }
if(flag[node]==1) {
 Refresh(node, b, e);
Refresh(node, b, e);
 }
flag[node] = 0;
 return;
}
 else if(b>=e) {
return;
 }
else {
 int mid = (b+e)>>1;
if(i<=mid) {
 update(2*node, b, mid, i, j);
}
 if(j>mid) {
update(2*node+1, mid+1, e, i, j);
 }
while(flag[2*node]>0) {
 Refresh(2*node, b ,mid);
}
 while(flag[2*node+1]>0) {
Refresh(2*node+1, mid+1, e);
 }
M1[node] = M1[node*2] + M1[2*node+1];
 M2[node] = M2[2*node] + M2[2*node+1];
}

}



int main() {
int N,m,u,v,ch;
 memset(M1,0,sizeof(M1));
memset(M2,0,sizeof(M2));
 memset(flag, 0, sizeof(flag));

 scanf("%d %d",&N,&m);
for(int i=0;ihttp://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Segment Tree Optimization

[Aamir Khan]

On Tue, Sep 27, 2011 at 1:27 PM, sunny agrawal wrote:

> implement segment tree with lazy propagation :)
>

What do you mean by lazy propagation ?

-- 
> Sunny Aggrawal
> B.Tech. V year,CSI
> Indian Institute Of Technology,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.
>



-- 
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.

[algogeeks] Segment Tree Optimization

[Aamir Khan]

I am trying to solve http://www.spoj.pl/problems/LITE/ using segment tree.
Here's the code but i am getting TLE. Can somebody help me to optimize the
code ?

#include
#include

struct node{
   int l;
   int r;
   bool el ;
   node *left;
   node *right;
};

struct node *build(int l, int r) {
   struct node *root = new node;
   root->l = l;
   root->r = r;
   root->el = 0;
   if(l==r) {
  root->left=NULL;
  root->right=NULL;
  return root;
   }
   root->left = build(l,(l+r)/2);
   root->right= build((l+r)/2+1,r);
   return root;
}

int query(struct node *root, int l, int r) {
   if(root==NULL || rel) && (root->l)<=l && (root->r)>=r) {
  return (r - l + 1);
   }

   int mid = (root->l + root->r)/2;
   return query(root->left, l, std::min(mid,r)) + query(root->right,
std::max(mid+1,l), r);

}

void update(struct node *root, int l,int r) {
   if(root->l==l && root->r==r && (root->left==NULL || root->el)) {
  root->el = 1 - root->el;
  return;
   }

   if(root->el) {
  root->left->el = 1;
  root->right->el = 1;
  root->el = 0;
   }

   int mid = (root->l + root->r)/2;
   if(l <= mid)
   update(root->left, l, std::min(mid,r));
   if(r > mid)
   update(root->right, std::max(mid+1,l), r);
}

int main() {
   int N, M;
   scanf("%d %d",&N,&M);
   struct node *root =   build(1,N);
   int L,R;
   int c;
   while(M--) {
      scanf("%d %d %d\n",&c,&L,&R);
  if(c==0)
  update(root, L, R);
  else
  printf("%d\n",query(root,L,R));
   }
   return 0;
}





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.

Re: [algogeeks] Re: Amazon online test

[Aamir Khan]

@shiv  :  Correct Answer should be  : 5C3 X 5 X 4 X3 = 600





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.

Re: [algogeeks] Re: Run for a google years

[Aamir Khan]

double n will overflow...

On 5/13/11, bittu  wrote:
> @Dave... I think 1 Googol Year is =10^100 not 10^116.5 ?? why u have
> used
>
> so then we have to write the single line program that googol years of
> time ??  & we have processor that can execute the instruction in 10^9
> per second  so the time required by googol year in second
>  which is equals to time t=pow(10,109)*365*86400 sec.
>
> so program is like
>
> #include 
> #include 
>
> int main() {
>
> double n = pow(10, 109) * 365 * 86400;
>
> while(n--);
> }
>
> Correct me if anything wrong???
>
> Thanks & Regards
> Shashank Mani>>"The Best Way To Escape From The problem is Solve It"
> Computer Science & Engg.
> BIT Mesra
>
> --
> 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
Indian Institute of Technology Roorkee,
Roorkee, Uttarakhand,
India , 247667
Phone: +91 9557647357
email:   aami...@iitr.ernet.in 
ak4u2...@gmail.com

-- 
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: Run for a google years

[Aamir Khan]

On Mon, May 9, 2011 at 8:31 PM, Don  wrote:

> That would do it if you have a 64-bit type, which most implementations
> have, but the standard does not require.
> I think that I can make it shorter and cleaner.
>
> int main(int argc, char* argv[])
> {
>const int n=49;
>char a[n]={0};
>int p=0;
>
>// This line will run for 10^100 years
>for(; p < n; p = ++a[p] ? 0 : p + 1);
>
>return 0;
> }
>
> The array of 49 bytes provides 392 bits of state, which will take more
> than the 2^387 cycles available in a google years.
>
> If the processor takes 9 operations to execute the loop, a value of
> n=48 would be sufficient.
>
>
Can you elaborate the 9 operations that execution of for loop will take.

 Don
>
> On May 7, 12:24 pm, Dave  wrote:
> > @Don: Here is my solution:
> >
> > unsigned long long int a=1;
> > unsigned long long int b=0;
> > unsigned long long int c=0;
> > unsigned long long int d=0;
> > unsigned long long int e=0;
> > unsigned long long int f=0;
> > unsigned long long int g=0;
> > unsigned long long int h=0;
> > /* here is the line "/
> > while(a)if(!++h)if(!++g)if(!++f)if(!++e)if(!++d)if(!++c)if(!++b)++a;
> >
> > My reasoning is as follows: 1 google years ~= 10^116.5 nanoseconds ~=
> > 2^387. Thus, incrementing an integer of length 387 bits once every
> > nanosecond should take a google years to overflow. Seven 64-bit
> > integers provides 448 bits of state.
> >
> > Dave
> >
> > On May 6, 11:25 am, Don  wrote:
> >
> > > What is the shortest single line in a C program which will take more
> > > than a google years to execute, but will eventually complete? You are
> > > permitted to have code before or after the line, but execution of the
> > > code must remain on that line, meaning no function calls, etc. Assume
> > > a processor which executes 1 billion operations a second.
> >
> >
>
> --
> 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
Indian Institute of Technology Roorkee,
Roorkee, Uttarakhand,
India , 247667
Phone: +91 9557647357
email:   aami...@iitr.ernet.in 
ak4u2...@gmail.com

-- 
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: Extract Top K elements from a List of N elements based on frequency

[Aamir Khan]

On Mon, May 9, 2011 at 11:44 AM, Ashish Goel  wrote:

> Dave,
> w.r.t statement, After all integers are processed, compress out the unused
> hash table
> entries and find the Kth largest element,
>
>
> I could not understand the compress concept...are you saying something on
> counting sort philosophy?
> say the list is
>
> 5
> 4
> 4
> 3
> 3
> 3
> 2
> 2
> 2
> 2
> 1
> 1
> 1
> 1
> 1
>
> so the hash map will have
>
> 5,1 <5 is 1 time>
> 4,2,<4 is two time>
> 3,3,...
> 2,4,...
> 1,5...
>
> so if the question is to find say 3rd largest element based on frequency,
> it would be 4
>

3rd largest element based on frequency should be 3 i think?


> This essentially means that we probably need dynamic order statistics where
> the node contains the starting rank for a particular entry in the RBTree.
> Each RBTree node contains the number, its frequency and rank. then this
> becomes O(n) +O(lgn) i.e. O(n)
>
>
>
>
>
>
>
>
>
>
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
>
> On Sat, May 7, 2011 at 11:03 PM, Dave  wrote:
>
>> @Gaurav: As I understand your solution, you are finding the K largest
>> integers based on value, rather than the K with the highest frequency
>> of occurrence.
>>
>> @Amit: Hash the integers into a hash table that includes a field for
>> the frequency count. When a new entry is made, set the frequency count
>> to 1. When an integer already is in the table, increment its count.
>> After all integers are processed, compress out the unused hash table
>> entries and find the Kth largest element. The overall algorithm can be
>> done in O(n).
>>
>> Dave
>>
>> On May 7, 12:06 pm, Gaurav Aggarwal <0007gau...@gmail.com> wrote:
>> > It can be done without sorting. Take the first element as pivot
>> > element. Calculate its position using Partition algorithm.
>> > If its new index is K, then on left side are top K  integers. If
>> index>K,
>> > apply algo on left side Else apply algo on right side.
>> >
>> > Best Case: O(1)
>> > Worst Case: O(n^2)
>> >
>> > But there are very less chances of worst case. It is when the list is
>> > already sorted.
>> >
>> >
>> >
>> >
>> >
>> > On Thu, May 5, 2011 at 1:06 AM, amit  wrote:
>> > > Hi ,
>> >
>> > > We are give a list of integers now our task is to find the top K
>> > > integers in the list based on frequency.
>> >
>> > > Apart from sorting the data can there be any other algorithm?
>> >
>> > > --
>> > > 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.
>> >
>> > --
>> > Gaurav Aggarwal
>> > SCJP- Hide quoted text -
>> >
>> > - Show quoted text -
>>
>> --
>> 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
Indian Institute of Technology Roorkee,
Roorkee, Uttarakhand,
India , 247667
Phone: +91 9557647357
email:   aami...@iitr.ernet.in 
ak4u2...@gmail.com

-- 
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: Run for a google years

[Aamir Khan]

On Mon, May 9, 2011 at 8:31 PM, Don  wrote:

> That would do it if you have a 64-bit type, which most implementations
> have, but the standard does not require.
> I think that I can make it shorter and cleaner.
>
> int main(int argc, char* argv[])
> {
>const int n=49;
>char a[n]={0};
>

I think we can use a single character like char a=0; instead of array of
characters as ultimately the value is incremented for a[0] only in your
code.

And i was testing with smaller values of n=1 and found something strange
like the value of a[p] increases from 0 to 127 (thats normal) but after
adding 1 to 127 it shows -128..I know that char is of 1byte or 8 bits only
and after +127 its value will overflow.

I have question regarding the same:

1) How to calculate the next value in case of overflow. As i tried
calculating by binary addition and 0111  + 1 = 1000  thats means
answer should have been -0 or 0.

   int p=0;
>
>// This line will run for 10^100 years
>for(; p < n; p = ++a[p] ? 0 : p + 1);
>
>return 0;
> }
>
> The array of 49 bytes provides 392 bits of state, which will take more
> than the 2^387 cycles available in a google years.
>
> If the processor takes 9 operations to execute the loop, a value of
> n=48 would be sufficient.


> Don
>
> On May 7, 12:24 pm, Dave  wrote:
> > @Don: Here is my solution:
> >
> > unsigned long long int a=1;
> > unsigned long long int b=0;
> > unsigned long long int c=0;
> > unsigned long long int d=0;
> > unsigned long long int e=0;
> > unsigned long long int f=0;
> > unsigned long long int g=0;
> > unsigned long long int h=0;
> > /* here is the line "/
> > while(a)if(!++h)if(!++g)if(!++f)if(!++e)if(!++d)if(!++c)if(!++b)++a;
> >
> > My reasoning is as follows: 1 google years ~= 10^116.5 nanoseconds ~=
> > 2^387. Thus, incrementing an integer of length 387 bits once every
> > nanosecond should take a google years to overflow. Seven 64-bit
> > integers provides 448 bits of state.
> >
> > Dave
> >
> > On May 6, 11:25 am, Don  wrote:
> >
> > > What is the shortest single line in a C program which will take more
> > > than a google years to execute, but will eventually complete? You are
> > > permitted to have code before or after the line, but execution of the
> > > code must remain on that line, meaning no function calls, etc. Assume
> > > a processor which executes 1 billion operations a second.
> >
> >
>
> --
> 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
Indian Institute of Technology Roorkee,
Roorkee, Uttarakhand,
India , 247667
Phone: +91 9557647357
email:   aami...@iitr.ernet.in 
ak4u2...@gmail.com

-- 
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: Square of Large integer

[AAMIR KHAN]

On Thu, Apr 14, 2011 at 9:08 PM, Dave  wrote:

> @AAmir: The easiest way is to declare A as long long int. Be sure to
> change the printf format string.
>
> I know that. But since i want to have only the last 9 digits of the answer
that can be accommodated in int only so there is no need for long long i
think.

>  Dave
>
> On Apr 14, 8:31 am, AAMIR KHAN  wrote:
> > #include
> > #define MOD (int)1e9
> > using namespace std;
> > int main() {
> >int A = 33554432;
> >printf("%d\n",A*A);
> >printf("%d\n",((A*A)%MOD));
> >return 0;
> >
> > }
> >
> > How can i calculate, lets say last 9 digits of square of 33554432 ?
> >
> > Thanks,
> > Aamir
>
> --
> 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: Square of Large integer

[AAMIR KHAN]

On Thu, Apr 14, 2011 at 7:40 PM, Akash Mukherjee  wrote:

> search nd read chinese remainder theorem
>
> please elaborate how can i use chinese remainder theorem.


> On Thu, Apr 14, 2011 at 7:04 PM, AAMIR KHAN  wrote:
>
>> *Output:*
>> 0
>> 0
>>
>>
>> On Thu, Apr 14, 2011 at 7:01 PM, AAMIR KHAN  wrote:
>>
>>> #include
>>> #define MOD (int)1e9
>>> using namespace std;
>>> int main() {
>>>int A = 33554432;
>>>printf("%d\n",A*A);
>>>printf("%d\n",((A*A)%MOD));
>>>return 0;
>>> }
>>>
>>> How can i calculate, lets say last 9 digits of square of 33554432 ?
>>>
>>>
>>>
>>>
>>> Thanks,
>>> Aamir
>>>
>>
>>  --
>> 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.

[algogeeks] Re: Square of Large integer

[AAMIR KHAN]

*Output:*
0
0

On Thu, Apr 14, 2011 at 7:01 PM, AAMIR KHAN  wrote:

> #include
> #define MOD (int)1e9
> using namespace std;
> int main() {
>int A = 33554432;
>printf("%d\n",A*A);
>printf("%d\n",((A*A)%MOD));
>return 0;
> }
>
> How can i calculate, lets say last 9 digits of square of 33554432 ?
>
>
>
>
> Thanks,
> Aamir
>

-- 
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.

[algogeeks] Square of Large integer

[AAMIR KHAN]

#include
#define MOD (int)1e9
using namespace std;
int main() {
   int A = 33554432;
   printf("%d\n",A*A);
   printf("%d\n",((A*A)%MOD));
   return 0;
}

How can i calculate, lets say last 9 digits of square of 33554432 ?




Thanks,
Aamir

-- 
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] suggestion required

[AAMIR KHAN]

You could try http://domjudge.sourceforge.net/ and do customizations in its
source code only..


On Thu, Mar 24, 2011 at 1:22 PM, .bashrc  wrote:

> Hi
> I have been working on  a progrmming judge that can be deployed in my
> college.I have already developed a prototype in bash.I want it to  be
> as
> general as possible,just like spoj,but i also want to add features to
> it
> like detecting copying of source code.Moreover to analyse the design
> of the code i
> need a source code parser,instead of plain gcc or any other compiler
> for
> other languages.Please give your opinions what more features we can
> add to
> the judge in context of academic use.I am currently working on gcc
> compiler
> to try some modification in it for analysing the design of code.But
> since i
> have to do the same for many other languages its prooving to be a
> daunting
> task.
> Saurabh Singh
> B.Tech (Computer Science)
> MNNIT ALLAHABAD
>
> --
> 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] An Interesting Question Calculate nth Power of Integer

[AAMIR KHAN]

Yeah i know the algorithm is not very much efficient...But i was trying to
show how to tackle with big integers in C++ (i.e, using arrays)

On Thu, Mar 24, 2011 at 1:06 PM, radha krishnan <
radhakrishnance...@gmail.com> wrote:

> You can do it in (log n) assuming multiplication is O(1)
> suppose u are going to calculate 8 power 33
> u compute 8 power 16 and multiply with the same to get 8 power 32
> then multiply with 8 to get the result
>
> On Thu, Mar 24, 2011 at 1:04 PM, AAMIR KHAN  wrote:
> > Try this...
> > #include 
> > #include 
> > using namespace std;
> > #define DIGITS 10001
> > void mult(int N,int pro[],int &len) {
> >int carry = 0;
> >for(int i=0;i >   int temp = pro[i]*N + carry;
> >   pro[i] = temp%10;
> >   carry = temp/10;
> >}
> >
> >if(carry>0) {
> >   pro[len] = carry;
> >   len++;
> >}
> >
> > }
> > int main() {
> >int t,N,E;
> >
> >scanf("%d",&t);
> >while(t--) {
> >   int pro[DIGITS];
> >   scanf("%d %d",&N,&E);
> >   if(N==1) {
> >   printf("1 1\n");
> >   continue;
> >   }
> >   pro[0] = 1; int len = 1;
> >   for(int i=0;i >mult(N,pro,len);
> >   }
> >
> >   for(int i=len-1;i>=0;i--) {
> >  printf("%d",pro[i]);
> >  }
> >   printf("\n");
> >
> >}
> >return 0;
> > }
> >
> > Here t stands for number of testcases...
> > N => the number for which power is to be calculated..
> > E => the exponent..
> > On Thu, Mar 24, 2011 at 12:22 PM, bittu 
> wrote:
> >>
> >> How you will print the 100th power of a single digit( which is of type
> >> int). How do you maintain that big number in memory?
> >>
> >>
> >> Lets C The Approach
> >>
> >> Thank & Regards
> >> Shashank
> >>
> >> --
> >> 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] An Interesting Question Calculate nth Power of Integer

[AAMIR KHAN]

Try this...

#include 
#include 

using namespace std;

#define DIGITS 10001

void mult(int N,int pro[],int &len) {
   int carry = 0;
   for(int i=0;i0) {
  pro[len] = carry;
  len++;
   }

}

int main() {
   int t,N,E;

   scanf("%d",&t);
   while(t--) {
  int pro[DIGITS];
  scanf("%d %d",&N,&E);
  if(N==1) {
  printf("1 1\n");
  continue;
  }
  pro[0] = 1; int len = 1;
  for(int i=0;i=0;i--) {
 printf("%d",pro[i]);
 }

  printf("\n");

   }
   return 0;
}


Here t stands for number of testcases...
N => the number for which power is to be calculated..
E => the exponent..

On Thu, Mar 24, 2011 at 12:22 PM, bittu  wrote:

> How you will print the 100th power of a single digit( which is of type
> int). How do you maintain that big number in memory?
>
>
> Lets C The Approach
>
> Thank & Regards
> Shashank
>
> --
> 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.