@ankit: pls explain the time complexity..
i dont think its O(log n)
On Thu, Jun 9, 2011 at 11:57 PM, ankit sambyal ankitsamb...@gmail.comwrote:
@Dumanshu: In each iteration, we r removing the smallest number. If
at any iteration we can't find the next smallest no., it means that
no. is
@ankit :please explain by taking an example.
On Fri, Jun 10, 2011 at 12:13 PM, Vetri Balaji vetribal...@gmail.comwrote:
@ankit: pls explain the time complexity..
i dont think its O(log n)
On Thu, Jun 9, 2011 at 11:57 PM, ankit sambyal ankitsamb...@gmail.comwrote:
@Dumanshu: In each
@Balaji: Sorry, the time complexity was not O(log n). It is O(n).
On Thu, Jun 9, 2011 at 11:43 PM, Vetri Balaji vetribal...@gmail.com wrote:
@ankit: pls explain the time complexity..
i dont think its O(log n)
On Thu, Jun 9, 2011 at 11:57 PM, ankit sambyal ankitsamb...@gmail.com
wrote:
can anyone explain Since there
are less than 2^32 numbers in the file there is bound to be one number
in the array that is less than 2^16. in dumanshu's solution.
On Fri, Jun 10, 2011 at 12:39 PM, varun pahwa varunpahwa2...@gmail.comwrote:
@ankit :please explain by taking an example.
On Fri,
http://www.spoj.pl/problems/THRBL/
my code is
i am getting TLE
# includeiostream
# includecstdio
using namespace std;
//int search(long long int [],long long )
int main()
{
while(1)
{
int n,m;
int count=0;
long long int a[50010]={0};
int b[50010],c[50010];
if((scanf(%d%d,n,m))==EOF)
break;
int
Lets say we have 9 numbers from 1 to 10 and one number is missing. We
hv a RAM which can accomodate only 3 nos.
9,6,7,4,3,2,1,5,10
So, we split the file into 3 smaller files each containing 3 nos.
File1: 9,6,7
File2: 4,3,2
File3: 1,5,10
Now take each file into memory one by one and min heapify
@ankit: think u missed heapify..
time complexity is O(n logn)
On Fri, Jun 10, 2011 at 12:55 PM, ankit sambyal ankitsamb...@gmail.comwrote:
Lets say we have 9 numbers from 1 to 10 and one number is missing. We
hv a RAM which can accomodate only 3 nos.
9,6,7,4,3,2,1,5,10
So, we split the file
@Balaji : No, I didn't miss it. Since we had broken the file
containing 300 million integers into smaller files containing much
less numbers. So, the time complexity of min heapify is not O(logn),
but it is O(log(no. of numbers in smaller file)), which is constant.
Correct if I am wrong.
On
There is a binary tree(Not a BST) in which you are given three nodes
x,y,z .Write a function which finds whether y lies in the path b/w x
and z.
--
Regards,*
Aanchal Goyal*.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this
42, 47
just guessing according to the pattern.
On Fri, Jun 10, 2011 at 1:37 PM, Lavesh Rawat lavesh.ra...@gmail.comwrote:
*Find next number in series
*
*
*
**
*What are the next two numbers in this sequence?
7, 14, 17, 21, 27, 28, 35, 37, ?, ?
* *
*
*Update Your Answers at* : Click
find common Ancestor of both. see if y lies on path from x or z to this
ancestor
O(lgn)
On Fri, Jun 10, 2011 at 1:20 PM, aanchal goyal goyal.aanch...@gmail.comwrote:
There is a binary tree(Not a BST) in which you are given three nodes
x,y,z .Write a function which finds whether y lies in the
can be solved using dfs.
On Fri, Jun 10, 2011 at 2:27 PM, sunny agrawal sunny816.i...@gmail.comwrote:
find common Ancestor of both. see if y lies on path from x or z to this
ancestor
O(lgn)
On Fri, Jun 10, 2011 at 1:20 PM, aanchal goyal
goyal.aanch...@gmail.comwrote:
There is a binary
@Karthik : Can you please the logic ??. Would be nice ..
On Fri, Jun 10, 2011 at 12:42 PM, kartik sachan kartik.sac...@gmail.comwrote:
http://www.spoj.pl/problems/THRBL/
my code is
i am getting TLE
# includeiostream
# includecstdio
using namespace std;
//int search(long long int [],long
what i understand from the problem was that.
n no of higests are given
and a and b and city no i.e from city a a ball is thrown to city no b
so i have done
from array a[] i.e hieght { n...no of times}
find all the element between b[i].city A and
Nothing is specified but lets take it as 2MB ram
On Jun 10, 10:14 am, hary rathor harry.rat...@gmail.com wrote:
dumnanshu
you should first mention memory size in your computer so that i could know
that how many number i can have in main memory at time
--
You received this message because
but that will be O(n) i think
On Fri, Jun 10, 2011 at 2:38 PM, Harshal hc4...@gmail.com wrote:
can be solved using dfs.
On Fri, Jun 10, 2011 at 2:27 PM, sunny agrawal sunny816.i...@gmail.comwrote:
find common Ancestor of both. see if y lies on path from x or z to this
ancestor
O(lgn)
@Sunny
I am assuming that the tree is rooted. There is no 'parent' pointer.
A
/ \
B C*
/ \
D* F*
/ \
J K
/ \
thats why i mentioned x OR z and i m considering parent pointer :)
without parent pointer both solutions will be O(n) :)
On Fri, Jun 10, 2011 at 3:02 PM, Harshal hc4...@gmail.com wrote:
@Sunny
I am assuming that the tree is rooted. There is no 'parent' pointer.
A
Hey the file has random 300 million numbers (9 digit)...there might be
duplicates... not a particular sequence out of the many missing
numbers we have to print just one... someone please try to understand
the solution given alongwith the question.
On Jun 10, 12:49 pm, ankit sambyal
42, 49
2011/6/10 • » νιρυℓ « • vipulmehta.1...@gmail.com
42, 47
just guessing according to the pattern.
On Fri, Jun 10, 2011 at 1:37 PM, Lavesh Rawat lavesh.ra...@gmail.comwrote:
*Find next number in series
* * ***
*
*
**
*What are the next two numbers in this sequence?
7, 14, 17,
@sunny agarwal : i dont think, it is O(lgn) its not a BST and further
u need to check for existence of
y in the path from lca to x or lca to z., so it l be O(n)..
On Jun 10, 1:57 pm, sunny agrawal sunny816.i...@gmail.com wrote:
find common Ancestor of both. see if y lies on path from x or z to
write an algo that deletes all negative integers without changing the
order of remaining elements of the queue
--
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
@ross if a parent pointer is there lca can be found in lgn
and path can be traversed in lgn too
why it cannot be lgn
what is the problem ??
On Fri, Jun 10, 2011 at 3:06 PM, sunny agrawal sunny816.i...@gmail.comwrote:
thats why i mentioned x OR z and i m considering parent pointer :)
without
First algorithm taht comes in mind
deque a element
if +ve enque again
if(-ve) do nothing
now question is terminating condition
On Fri, Jun 10, 2011 at 3:44 PM, Sangeeta sangeeta15...@gmail.com wrote:
write an algo that deletes all negative integers without changing the
order of remaining
@ankur..how did you get that...explain..plz
On Fri, Jun 10, 2011 at 3:11 AM, ankur aggarwal aggarwal11...@gmail.comwrote:
42, 49
2011/6/10 • » νιρυℓ « • vipulmehta.1...@gmail.com
42, 47
just guessing according to the pattern.
On Fri, Jun 10, 2011 at 1:37 PM, Lavesh Rawat
initialy cal size of queue then apply a for loop
On Fri, Jun 10, 2011 at 4:00 PM, sunny agrawal sunny816.i...@gmail.comwrote:
First algorithm taht comes in mind
deque a element
if +ve enque again
if(-ve) do nothing
now question is terminating condition
On Fri, Jun 10, 2011 at 3:44 PM,
i agree with the logici also implemented it...and getting TLE...there
must exist some better method :(
On Fri, Jun 10, 2011 at 2:18 AM, kartik sachan kartik.sac...@gmail.comwrote:
what i understand from the problem was that.
n no of higests are given
and a and b and city no
@sunny finding lca in logn is fine, but how can we traverse the path in
logn.. ?
On Fri, Jun 10, 2011 at 3:50 PM, sunny agrawal sunny816.i...@gmail.comwrote:
@ross if a parent pointer is there lca can be found in lgn
and path can be traversed in lgn too
why it cannot be lgn
what is the
how should we get TLE loop total running less than 10^6??
--
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
using parent pointers untill we reach to lca.
On Fri, Jun 10, 2011 at 3:59 PM, aanchal goyal goyal.aanch...@gmail.comwrote:
@sunny finding lca in logn is fine, but how can we traverse the path in
logn.. ?
On Fri, Jun 10, 2011 at 3:50 PM, sunny agrawal sunny816.i...@gmail.comwrote:
@ross
may be 42,47. actually table of seven and a digit 7.
On Fri, Jun 10, 2011 at 3:29 AM, nicks crazy.logic.k...@gmail.com wrote:
@ankur..how did you get that...explain..plz
On Fri, Jun 10, 2011 at 3:11 AM, ankur aggarwal
aggarwal11...@gmail.comwrote:
42, 49
2011/6/10 • » νιρυℓ « •
@sunny. ..lol..dude..20 June is My Bro's B'day 18th Nov is of My
mom ...:P
Shashank
Computer Science Engg.
Birla Institute of Technology, Mesra
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
42,50
On Jun 10, 3:29 pm, nicks crazy.logic.k...@gmail.com wrote:
@ankur..how did you get that...explain..plz
On Fri, Jun 10, 2011 at 3:11 AM, ankur aggarwal
aggarwal11...@gmail.comwrote:
42, 49
2011/6/10 • » νιρυℓ « • vipulmehta.1...@gmail.com
42, 47
just guessing
42,47
On Fri, Jun 10, 2011 at 4:50 PM, abhishekriyer
abhishekr.iye...@gmail.comwrote:
42,50
On Jun 10, 3:29 pm, nicks crazy.logic.k...@gmail.com wrote:
@ankur..how did you get that...explain..plz
On Fri, Jun 10, 2011 at 3:11 AM, ankur aggarwal aggarwal11...@gmail.com
wrote:
Use Range Maximum Query.
On Fri, Jun 10, 2011 at 4:15 PM, kartik sachan kartik.sac...@gmail.comwrote:
how should we get TLE loop total running less than 10^6??
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group,
Yups...that seems best.. :)
On Fri, Jun 10, 2011 at 4:03 PM, sunny agrawal sunny816.i...@gmail.comwrote:
initialy cal size of queue then apply a for loop
On Fri, Jun 10, 2011 at 4:00 PM, sunny agrawal sunny816.i...@gmail.comwrote:
First algorithm taht comes in mind
deque a element
if
u construct a tree nlogn , every node answers a query.. (or u get ans with a
recursion) in log(n) , so when u r doing a lot of query RMQ proves to be
very fast
On Fri, Jun 10, 2011 at 6:28 PM, nicks crazy.logic.k...@gmail.com wrote:
ya i saw that in the comments on spoj someone suggested to use
Suppose you are given an array a[]={2,3,1,4,6,7,10}
now for successfully transferring the ball,from ith city to jth city,a[i]
max(a[i..j-1]).
A naive approach would be to calculate all possible max[i][j] that is max
for each interval and then answer the query in 0(1) time.Another approach
would
How do you reverse the bits between j to k in a 32 bit integer.
For e.g.:
n = 11100011; j = 2 and k = 5
output: 1101 (bits from 2 to 5 are reversed.)
n = 11010110; j = 1 and k = 5
output: 11101000
O(1) method is preferred.
Thanks,
--
Dinesh Bansal
The Law of Win says, Let's not do it
since a queue is given ...only queue operations are allowed
just dequeue all elements from the queue and if a number is +ve enqueue them
to other queue
after this just copy the 2nd queue to 1st one
O(n)
On Fri, Jun 10, 2011 at 3:44 PM, Sangeeta sangeeta15...@gmail.com wrote:
write an algo that
anything that is declared volatilecompiler dont apply its optimization
on that storage
i.e it dont remove the redundant memory accesses
in case of a normal volatile variable ,its value is checked everytime it is
used in the program
compiler dont make any assumptions
similarly in case of
Take n from user and print 1 to n. No loops like for/while/do-while are
allowed to use.
--Navneet
--
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,
so what ? supporting anna hazare is not a bad idea.
On Thu, Jun 9, 2011 at 12:54 PM, Naveen Kumar naveenkumarve...@gmail.comwrote:
There is no such condition put up by the govt.
If you give a missed call you are showing your support to Anna Hazare
Please read
just visit spoj forums
On Fri, Jun 10, 2011 at 9:42 AM, keyan karthi keyankarthi1...@gmail.comwrote:
the nos can repeat :) ie the valid set may contain multiple instance of a
same number..
hope this helps :)
On Fri, Jun 10, 2011 at 9:31 AM, saurabh singh saurab...@gmail.comwrote:
ex-or operation on all the elements give you the answer.
On Jun 9, 5:45 am, Dumanshu duman...@gmail.com wrote:
Q1. I have a file in which there are supposed to be 4 billion
numbers,
starting from 1 to 4,000,000,000 but unfortunately one number is
missing,
i.e there are only 3,999,999,999
I think you don't need other queue to do this, simply enqueue the
non-negative dequeued element to the original queue.
On Fri, Jun 10, 2011 at 11:32 AM, ADITYA KUMAR aditya...@gmail.com wrote:
since a queue is given ...only queue operations are allowed
just dequeue all elements from the queue
Can goto statement be used?
On Fri, Jun 10, 2011 at 11:42 AM, Navneet Gupta navneetn...@gmail.comwrote:
Take n from user and print 1 to n. No loops like for/while/do-while are
allowed to use.
--Navneet
--
You received this message because you are subscribed to the Google Groups
IF allowed ???
If yes...Use recursion..
On Fri, Jun 10, 2011 at 9:12 PM, Navneet Gupta navneetn...@gmail.comwrote:
Take n from user and print 1 to n. No loops like for/while/do-while are
allowed to use.
--Navneet
--
You received this message because you are subscribed to the Google
No.
On Fri, Jun 10, 2011 at 9:26 PM, nagajyothi gunti
nagajyothi.gu...@gmail.com wrote:
Can goto statement be used?
On Fri, Jun 10, 2011 at 11:42 AM, Navneet Gupta navneetn...@gmail.comwrote:
Take n from user and print 1 to n. No loops like for/while/do-while are
allowed to use.
Using recursion would be like using loops only. Also i believe the recursion
used would be tail recursion and one can change tail recursion to loop based
non recursive method.
Okay, giving all a hint. Think classes and objects.
On Fri, Jun 10, 2011 at 9:26 PM, Navneet Gupta
we can declare a class with construction printing value
class A
{
private:
static int i;
public:
A()
{
cout++i endl;
}
};
A::i=0;
main()
{
int n=5;
A ob[n];
}
this will print from 1 to 5
am i right?
On Fri, Jun 10, 2011 at 9:30 PM, Navneet Gupta navneetn...@gmail.comwrote:
Using recursion
Good Answer Radhika. You are correct.
On Fri, Jun 10, 2011 at 9:40 PM, Radhika Renganathan
radi.coo...@gmail.comwrote:
we can declare a class with construction printing value
class A
{
private:
static int i;
public:
A()
{
cout++i endl;
}
};
A::i=0;
main()
{
int n=5;
A ob[n];
}
sorry i meant 'constructor' !
On Fri, Jun 10, 2011 at 9:40 PM, Radhika Renganathan
radi.coo...@gmail.comwrote:
we can declare a class with construction printing value
class A
{
private:
static int i;
public:
A()
{
cout++i endl;
}
};
A::i=0;
main()
{
int n=5;
A ob[n];
}
this
this problem was discussed some time before on this group
i am picking up a solution discussed there which you would love to see
int i=1;
#define PRINT1 couti++endl;
#define PRINT2 PRINT1 PRINT1
#define PRINT4 PRINT2 PRINT2
#define PRINT8 PRINT4 PRINT4
#define PRINT16 PRINT8 PRINT8
#define
hi frndz
given an array which is circularly sorted like
6 ,7,8 ,1 ,2 ,3 ,4,5
search a given number.
--
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
42,47
--
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/-/mi5D7Az5nssJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this
How about this???
*
unsigned int flip_j_to_k_bits (unsigned int n,unsigned int j,unsigned int k)
{
unsigned int temp;
int num_of_on_bits = k-j+1;
temp = (1num_of_on_bits)-1;
temp = j;
return (n^temp);
}*
I dont know whether shift operation is O(1) or not !
But i think
@Aditya; Thanks..
--
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/-/UO6vAXBXhXEJ.
To post to this group, send email to algogeeks@googlegroups.com.
To
int flip(int j,int k,int n)
{
int t1=(1j)-1;
int t2=(1k)-1;
t1=t2^t1;
return n^t1;
}
correct me if im wrong
On Fri, Jun 10, 2011 at 10:09 PM, Kunal Patil kp101...@gmail.com wrote:
How about this???
*
unsigned int flip_j_to_k_bits (unsigned int n,unsigned int j,unsigned int
k)
{
Use ternary search to find the minimum number. (In this case 1)
Then you have two sorted arrays, one ascending and one descending.
Now, you can apply binary search. First, check the number with the
last element and the first element and chose the appropriate array for
searching.
Time complexity:
@ross: seems logically correct..nice 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.
To unsubscribe from this group, send email to
Y do we need to deque and enque the nodes again the problem is similar
to the node given in the linked list and delete that node.
solution is :
copy the next node data to the node to be deleted(ie node holding -ve
number) and delete the next node.
in this way order won't be changed.
Correct me if
in this question i assumed that we need to write a function which takes an
input a queue and function implements the required.
we don't know how the queue is implemented, means we don't know about
structure of the node.
only 2 standard functions of queue enqueue and dequeue are known
On Fri, Jun
42, 47
On Fri, Jun 10, 2011 at 9:57 PM, shashankreddy509
shashankreddy...@gmail.com wrote:
42,47
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
@ Dumanshu:
With memory restriction also XOR method works.. :)
In this case difference is just that you will be working with 400/ X
number of files..where X is size of the RAM...just maintain a variable
Curr_XOR_value and go on XORing it with element read from the file.
When you are done
Binary search is sufficient for this particular case.
To help the explain, we assume the circular sorted array is ascending if
probably rotated. we use *d[0..n - 1]* to represent the array
with n elements and *v* to represent the searched number.
Observing the circular sorted sequence d[0..n -
This is the link to the SPOJ problem HASHIT :
http://www.spoj.pl/problems/HASHIT/
i donno whts the mistake... i keep getting wrong answer even though
the Q is Straightforward :(
#includeiostream
#includestring
using namespace std;
int hash(string str)
{
int sum = 0;
int len =
Search Topcoder Tutorial Range Minimum Query @ Google...
By few intuitive changes u can implement Range Maximum Query as well...
--
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.
@kunal: could u plz explan ur XOR approach by using a small set of
numbers. lets say we have numbers from 1 to 5 and one number is
missing. so u mean 1 XOR 2 XOR 4 XOR 5 would give me 3???
On Jun 10, 11:41 pm, Kunal Patil kp101...@gmail.com wrote:
@ Dumanshu:
With memory restriction also XOR
@kunal... yeah it will work. thnx :)
On Jun 10, 11:41 pm, Kunal Patil kp101...@gmail.com wrote:
@ Dumanshu:
With memory restriction also XOR method works.. :)
In this case difference is just that you will be working with 400/ X
number of files..where X is size of the RAM...just
We know the size (number of elements) of the queue right?
On Jun 10, 1:33 pm, ADITYA KUMAR aditya...@gmail.com wrote:
@monang wats the terminating codition..??
On Fri, Jun 10, 2011 at 9:21 PM, Monang Setyawan mon...@gmail.com wrote:
I think you don't need other queue to do this,
Mr. White
On Wed, Jun 8, 2011 at 8:07 PM, amit kumar amitthecoo...@gmail.com wrote:
Mr. White
On Wed, Jun 8, 2011 at 2:30 PM, nicks crazy.logic.k...@gmail.com wrote:
what does the highest chance of survival ? mean.. is it about black's
survival or overall survival.i'm confused
@balaji: right , just one change required i think so coz in question they
are asking for change of one more bit i.e. for j=2,k=5.. bits 2,3,4,5 are
modified..ur code is doing i guess only 2,3,4.. i think just one change
needed int t2=(1(k+1))-1;
On Fri, Jun 10, 2011 at 10:22 PM, Vetri Balaji
no..it will work just fine
On Sat, Jun 11, 2011 at 3:31 AM, Anika Jain anika.jai...@gmail.com wrote:
@balaji: right , just one change required i think so coz in question they
are asking for change of one more bit i.e. for j=2,k=5.. bits 2,3,4,5 are
modified..ur code is doing i guess only
74 matches
Mail list logo
