Number exponentiation
On Fri, Jan 21, 2011 at 1:05 PM, snehal jain learner@gmail.com wrote:
Given M, find if M = 3^x for some positive integer x efficiently. DO
NOT think of log, pow etc
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
*
Place N number from 1 to N, in 2N positions in such a way so that there are
Exactly “a” number of cells between two placed locations of number “a”.
Write a program to display numbers placed in this way.
Example:-
(1) One of the possible placement for 7 numbers in 14 positions is :
5 7 2 3
You have a dictionary of N words each of 3 chars. Given 2 words you
have to find the optimum path between the 2 words. The optimum path
contains the words in the dictionary each word at a distance of 1 from
the previous word.
for eg source = cat , target = sun
path is
cat - bat - but - bun - sun
Suppose you have a tree. A binary tree (for something like
simplicity :p). You are traversing it (using infix, postfix or prefix)
to search for a node. You find your required node. You just realized
that you need to know the path from this node back to the root node
(and/or vice versa). Given the
Here is solution from Igor
Naverniouk(Google): http://shygypsy.com/tools/pairsums.cpp
--
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
binary search on the answer and then fast exponentiation.
--
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
The most well done solution is to store possible powers of 3 in a table
(this table will be small), and then try to find number M.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
@ above
m nt getting binary search and fast exponentiation .. please elaborate.
On Fri, Jan 21, 2011 at 2:07 PM, juver++ avpostni...@gmail.com wrote:
The most well done solution is to store possible powers of 3 in a table
(this table will be small), and then try to find number M.
--
You
@ above
cn u please explain your logic.
On Fri, Jan 21, 2011 at 2:02 PM, juver++ avpostni...@gmail.com wrote:
Here is solution from Igor Naverniouk(Google):
http://shygypsy.com/tools/pairsums.cpp
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
Magy! receives a huge amount of queries everyday. They don’t want to
store all of them, since many of the queries are unique (submitted
just one time by just one user). Anyway, for caching reason they want
to understand what are the queries whose frequency exceed s=0.1%. How
do you solve the
Given an unsorted array A of n distinct numbers and an integer k where
1 = k = n, design an algorithm that finds the k numbers in A that
are closest in value to the median of A in O(n) time.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To
In this variation of the Maximum-Sum Subarray Problem, you are given a
one-dimensional array A[1 : n] of positive or negative numbers, and
you are asked to find a subarray A[i : j] such that the sum of its
elements is (1) strictly greater than zero, and (2) minimum. In other
words, you want to
You are given two height balanced binary search trees T and T’,
storing m and n elements respectively. Every element of tree T is
smaller than every element of tree T’. Every node u also stores height
of the subtree rooted at it. Using this extra information how can you
merge the two trees in time
int l = 0, r = ...;
while (l r) {
int m = (l + r) / 2;
int p = power(3, m);
if (p M) r = m - 1;
else if (p M) l = m + 1;
else print 3^m = M;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
http://www.topcoder.com/tc?module=Staticd1=match_editorialsd2=srm182
--
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
Given an array of integers where some numbers repeat 1 time, some
numbers repeat 2 times and only one number repeats 3 times, how do you
find the number that repeat 3 times.
please give if you have solution other than hashing and sorting..
--
You received this message because you are subscribed
Below is code for modular exponentation in general
// (a^b)%c
int modexp(int a,int b,int c)
{
int ans=1;
while(b)
{
if(b1) ans=(ans*a)%c;
a=(a*a)%c;
b=1;
}
return ans;
}
On Fri, Jan 21, 2011 at 3:27 PM, juver++ avpostni...@gmail.com wrote:
int l = 0, r = ...;
How about this dp solution?
Let dp[i][j][k] be the lookup table.
It is defined as the longest zigzag sequence in the range i and j. k is
either 0 or 1.
0- if the sequence ends with a positive difference, i.e last element is
greater than the last to one.
1- if the sequence ends with a negative
this will be O(log(n) * log(n)) solution
On Fri, Jan 21, 2011 at 4:29 PM, abhijith reddy abhijith200...@gmail.comwrote:
Below is code for modular exponentation in general
// (a^b)%c
int modexp(int a,int b,int c)
{
int ans=1;
while(b)
{
if(b1) ans=(ans*a)%c;
@juvir++
it was mentioned in question not to use log or power. isnt there any
approach using bitwise operators
On Fri, Jan 21, 2011 at 5:24 PM, Manmeet Singh mans.aus...@gmail.comwrote:
this will be O(log(n) * log(n)) solution
On Fri, Jan 21, 2011 at 4:29 PM, abhijith reddy
O(lg(n)*lg(n)) is the complexity of the solution ! Not the solution.
M=3^x
We binary search on x and then compute 3^x in log(x) time using
exponentiation. Hence the complexity.
On Fri, Jan 21, 2011 at 5:50 PM, snehal jain learner@gmail.com wrote:
@juvir++
it was mentioned in question not
@snehal .. misread it .. my apologies.
On Fri, Jan 21, 2011 at 5:56 PM, abhijith reddy abhijith200...@gmail.comwrote:
O(lg(n)*lg(n)) is the complexity of the solution ! Not the solution.
M=3^x
We binary search on x and then compute 3^x in log(x) time using
exponentiation. Hence the
@snehal : YUP
On Fri, Jan 21, 2011 at 5:57 PM, abhijith reddy abhijith200...@gmail.comwrote:
@snehal .. misread it .. my apologies.
On Fri, Jan 21, 2011 at 5:56 PM, abhijith reddy
abhijith200...@gmail.comwrote:
O(lg(n)*lg(n)) is the complexity of the solution ! Not the solution.
M=3^x
Find the node in T which is the maximum(which is either the root or the
rightmost in the right subtree).
After finding this node, just make the right child of this node point to the
root of T'.
Correct me if i am wrong
On Fri, Jan 21, 2011 at 2:43 PM, snehal jain learner@gmail.com wrote:
@above it's a user-defined function using fast exponentiation
--
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
@juver++ : the above is a user defined function. but its possible to the
problem using bit wise operators.
On Fri, Jan 21, 2011 at 7:29 PM, juver++ avpostni...@gmail.com wrote:
@above it's a user-defined function using fast exponentiation
--
You received this message because you are
Its a state space search. Solve it by using any of the known search
algorithms.
BFS, Best first search, DFS, A*
On Fri, Jan 21, 2011 at 2:00 PM, snehal jain learner@gmail.com wrote:
You have a dictionary of N words each of 3 chars. Given 2 words you
have to find the optimum path between
@manmeet
how?
On Fri, Jan 21, 2011 at 7:36 PM, Manmeet Singh mans.aus...@gmail.comwrote:
@juver++ : the above is a user defined function. but its possible to the
problem using bit wise operators.
On Fri, Jan 21, 2011 at 7:29 PM, juver++ avpostni...@gmail.com wrote:
@above it's a
How do you find out the fifth maximum element in an binary search tree
in efficient manner without using any extra 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
This question was posted some time ago.
One solution is - start from the largest element (which is the righmost one
in the tree).
Then apply algorithm of searchin node's predecessor. It takes O(k) time to
find k-th largest/smallest number.
--
You received this message because you are
write n, n-1 to base 3
check if thr gives 0, if it gives no. is of form 3^n
On Fri, Jan 21, 2011 at 8:04 PM, snehal jain learner@gmail.com wrote:
@manmeet
how?
On Fri, Jan 21, 2011 at 7:36 PM, Manmeet Singh mans.aus...@gmail.comwrote:
@juver++ : the above is a user defined function.
wow..thank you so much
On Wed, Jan 19, 2011 at 2:08 PM, LALIT SHARMA lks.ru...@gmail.com wrote:
--
Lalit Kishore Sharma,
IIIT Allahabad (Amethi Capmus),
6th Sem.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group,
Assume you are writing number in ascending order to an array of constant
size.once you reach the end of the array,you start writing from the
beginning, thus writing over the oldest entries.Write an algorithm for
finding a specific number in this array.
--
You received this message because you
http://www.ocf.berkeley.edu/~wwu/riddles/intro.shtml
Rahul K Rai
rahulpossi...@gmail.com
On Tue, Jan 18, 2011 at 9:27 PM, Yellow Sapphire pukhraj7...@gmail.comwrote:
Hi,
Can someone suggest good books/websites/blogs for interview related
questions.
thanks--
YS
--
You received this
Thanks , btw the example was from Dragon Book of Compilers . . Any one
knows an instructor manuall or some selected set of solutions for that
. ? I have read it that they are not published
On 1/21/11, Gene gene.ress...@gmail.com wrote:
L and R values have great significance to language designers
One more interesting site is http://www.rawkam.com
-Original Message-
From: algogeeks@googlegroups.com [mailto:algogeeks@googlegroups.com] On
Behalf Of awesomeandroid
Sent: 19 January 2011 AM 09:15
To: Algorithm Geeks
Subject: [algogeeks] Re: Sites for Interview Questions
Programming Interviews Exposed is a good one..
On Tue, Jan 18, 2011 at 9:27 PM, Yellow Sapphire pukhraj7...@gmail.comwrote:
Hi,
Can someone suggest good books/websites/blogs for interview related
questions.
thanks--
YS
--
You received this message because you are subscribed to the
if sorted then a tweak in merge sort will work
On 20 January 2011 23:23, nishaanth nishaant...@gmail.com wrote:
Ya as Ashish said hashing is the best solution :)
On Fri, Jan 14, 2011 at 6:00 PM, Ashish Goel ashg...@gmail.com wrote:
ideally, a hashMap would be preferred
walk through one
@ above height will not be balanced then
On 21 January 2011 19:15, nishaanth nishaant...@gmail.com wrote:
Find the node in T which is the maximum(which is either the root or the
rightmost in the right subtree).
After finding this node, just make the right child of this node point to
the root
hope this works :
#includestdio.h
#define MAX(A,B) AB?A:B
#defineMIN(A,B) AB?A:B
int FindMaxA(int n)
{
int i,k,factor,max = 0,cur,prev;
int* arr = new int[n+1];
int p = MIN(n,4);
for( int j = 1;j = p;j++)
arr[j] = j;
for(i=5;i=n;i++)
{
k = i-4;
@nishaanth can u give the outline?//
On 1/21/11, nishaanth nishaant...@gmail.com wrote:
Its a state space search. Solve it by using any of the known search
algorithms.
BFS, Best first search, DFS, A*
On Fri, Jan 21, 2011 at 2:00 PM, snehal jain learner@gmail.com wrote:
You have a
@fight good solution.
3^n contains only one 1 in the 3-base representation.
So write number M in base-3, and check if it contains only one digit(1).
There is no need to find with M-1.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post
@ juver++ : fight is my tc handle. here u can call me manmeet :) :)
On Fri, Jan 21, 2011 at 9:35 PM, juver++ avpostni...@gmail.com wrote:
@fight good solution.
3^n contains only one 1 in the 3-base representation.
So write number M in base-3, and check if it contains only one digit(1).
how merge sort ?/
On Thu, Jan 20, 2011 at 11:23 PM, nishaanth nishaant...@gmail.com wrote:
Ya as Ashish said hashing is the best solution :)
On Fri, Jan 14, 2011 at 6:00 PM, Ashish Goel ashg...@gmail.com wrote:
ideally, a hashMap would be preferred
walk through one array and set the
Ok lets define the following functions.
movegen()- gives the list of next move given the state. This is basically
all the 1 distance words given the current word.
heuristic()- this gives the number of non-matching characters of the given
word with the goal word.
Start from start state and
Thanks so much
On Wed, Jan 19, 2011 at 4:20 AM, jayapriya surendran priya7...@gmail.comwrote:
wow..thank you so much
On Wed, Jan 19, 2011 at 2:08 PM, LALIT SHARMA lks.ru...@gmail.com wrote:
--
Lalit Kishore Sharma,
IIIT Allahabad (Amethi Capmus),
6th Sem.
--
You received this
@Juver..doesnt it require the parent information ?
What if the data structure has only left and right pointers.
On Fri, Jan 21, 2011 at 8:41 PM, juver++ avpostni...@gmail.com wrote:
This question was posted some time ago.
One solution is - start from the largest element (which is the righmost
whts complexity for this movegen()
On Fri, Jan 21, 2011 at 9:52 PM, nishaanth nishaant...@gmail.com wrote:
Ok lets define the following functions.
movegen()- gives the list of next move given the state. This is basically
all the 1 distance words given the current word.
heuristic()- this
@manmeet so, please choose your nickname at the forum :)
--
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
@above yes, posted solution needs parent links.
Another solution is to process tree in reverse inorder: right subtree, root,
left subtree and keeping counter k,
when k is zero return current node
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
It's really good. Thanks a lot
On Fri, Jan 21, 2011 at 8:24 AM, Sreeprasad Govindankutty
sreeprasad...@gmail.com wrote:
Thanks so much
On Wed, Jan 19, 2011 at 4:20 AM, jayapriya surendran
priya7...@gmail.comwrote:
wow..thank you so much
On Wed, Jan 19, 2011 at 2:08 PM, LALIT SHARMA
My Pleasure !!
On Fri, Jan 21, 2011 at 11:22 PM, Anand anandut2...@gmail.com wrote:
It's really good. Thanks a lot
On Fri, Jan 21, 2011 at 8:24 AM, Sreeprasad Govindankutty
sreeprasad...@gmail.com wrote:
Thanks so much
On Wed, Jan 19, 2011 at 4:20 AM, jayapriya surendran
You are given a bst where each node has a int value , parent pointer , and
left and right pointers , write a function to find a path with a given sum
value. Path can go from left subtree tree , include root and go to right
tree as well . we need to find these paths also .
5
/ \
1 10
/ \ / \
0
Given a distribution of packages on media and a list of dependences
between packages, you have to calculate the minimal number of media
changes required to install all packages. For your convenience, you
may assume that the operating system comes on exactly 2 DVDs.
Yes, you are right
--
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
Within a 2D space, there is a batch of points(no duplicate) in the
region (0,0),(0,1),(1,0),(1,1), try to find a line which can divide
the region to 2 parts with half points in each .the input will be an
array of points and the length of the array.
struct point{
int x;
int y;
};
input : struct
can u give me sipser solution mannual?
On 1/21/11, Sreeprasad Govindankutty sreeprasad...@gmail.com wrote:
Thanks so much
On Wed, Jan 19, 2011 at 4:20 AM, jayapriya surendran
priya7...@gmail.comwrote:
wow..thank you so much
On Wed, Jan 19, 2011 at 2:08 PM, LALIT SHARMA
We can also use jagged arrays for this purpose
int[][] symmetric_matrix = new int[size][];
for (int i=0; i size; i++)
...symmetric_matrix[i]=new int[max_diagonal/(size)];
On Wed, Jan 12, 2011 at 9:30 AM, Sathaiah Dontula don.sat...@gmail.comwrote:
1 + 2 + + n ( max diagonal) = n (
Given n points on a 2D coordinate system . What is the most efficient
way of finding nearest point for each point? How can we find all the
points at a distance k from a given point efficiently?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
--
*Piyush Verma*
*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
if both arrray are sorted. take two ptrs, one pointing to a[0] other to
b[0]. if elements are same then nt disjoint. else increment ptr pointing to
smaller element until it becomes equal or greater than the element pointed
by other. repeat until either ptr reaches end of array..
On 21 January
@Divya: The coordinates of the points are between 0 and 1 and are
integers. That can't be right.
Dave
On Jan 21, 1:46 pm, divya sweetdivya@gmail.com wrote:
Within a 2D space, there is a batch of points(no duplicate) in the
region (0,0),(0,1),(1,0),(1,1), try to find a line which can divide
It will be like a circularly sorted array.There exists a binary search type
divide and conquer mechanism to find a specific number in such type of
arrays.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
Given an integer array of which both first half and second half are
sorted. Write a function to merge the two parts to create one single
sorted array in place [do not use any extra space].
e.g. If input array is [1,3,6,8,-5,-2,3,8] It should be converted to:
[-5,-2,1,3,3,6,8,8]
i have thought of
64 matches
Mail list logo
