@bittu
Question is about to print entire array in sorted order, not searching an
element
On Wed, Mar 2, 2011 at 4:13 AM, bittu shashank7andr...@gmail.com wrote:
@all after 32 Message Discussion I know Everyone is looking for O(N)
solution well it seems odd how we can search an element in a
Hii, can you please tell me wat d ques exactly is ??
THanks,
Krishna.
On Wed, Mar 2, 2011 at 9:52 AM, sunny agrawal sunny816.i...@gmail.comwrote:
@bittu
Question is about to print entire array in sorted order, not searching an
element
On Wed, Mar 2, 2011 at 4:13 AM, bittu
You are given a array with rows sorted and column sorted. You have to print
entire array in sorted order.
--
Sunny Aggrawal
B-Tech IV 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
We can use count sort for this. Its intermediate step just tell us the
frequency of each number.
and its complexity is just O(n).
--
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.
But count sort is not applicable for large number of input.In that case what
should be done?
--
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
@Mannu: Suppose that a[k] = k*k for every even value of k, and the
a[k] for odd values of k are such that the conditions of the problem
hold; i.e., every value in a[] occurs 1, 2, or 3 times, with only one
value occurring 3 times. Then what is your data structure so that the
task is O(n)?
Dave
@Gaurav Hey I forgot to say Hashing is not allowed sum thing other
then this better solution
@radha i don't think ur method works here chk out ur method
http://codepad.org/oTDNSoeu
Thanks
Shashank
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
If hashing is disallowed, then I think the best method is to sort the
data and check for consecutive triplicates. O(n log n).
Dave
On Feb 27, 6:35 am, bittu shashank7andr...@gmail.com wrote:
@Gaurav Hey I forgot to say Hashing is not allowed sum thing other
then this better solution
@radha i
i agree with dave...Sorting seems to be best method until you know something
more about type and limitations on the data present...If input has any
random numbers then sorting is best if no hashing is permitted...
On Sun, Feb 27, 2011 at 7:15 PM, Dave dave_and_da...@juno.com wrote:
If hashing
@Radha: Please explain your method further. You can use this data:
0, 1, 2, 4, 4, 5, 5, 6, 6, 6.
Dave
On Feb 26, 10:44 am, radha krishnan radhakrishnance...@gmail.com
wrote:
XOR :P
On Sat, Feb 26, 2011 at 10:11 PM, bittu shashank7andr...@gmail.com wrote:
Given an array of integers where
Kind of brute force with O(n*log(n))
map mint, int;
for( int i=0; iN; i++)
m[a[i]]++;
for each element in hashmap
if( m[i] == 3)
print i;
On Sun, Feb 27, 2011 at 3:59 AM, Dave dave_and_da...@juno.com wrote:
@Radha: Please explain your method further. You can use this data:
Look up the Subset Sum problem. I think you may find that you can
put together a hybrid algorithm based on the classic method of
performing subset sum calculations. I did something similar a few
years back. It worked out pretty good as I recall.
Dan:-)
--
You received this message
In O(n^2). Sort two of the arrays, say B and C, into ascending order.
For each element in A, search forward in B and backwards in C looking
for a zero sum. Something like this, using zero-based arrays of length
n:
int i, j, k;
for( i = 0 ; i n ; ++i )
{
j = 0;
k = n-1;
while( (j n)
I am not very sure i understood what you meant and if your suggestion
reduces the comparisons. Please see the code i posted at
https://github.com/algoseeker/Interview/blob/master/sorting/SortArray.java
and tell me what changes you are talking about.
--
You received this message because you
I am using a minheap and not a set if you see carefully.
--
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
I am using a minheap (similar to priority queue) and order of extra space is
at O(n+m) which in fact is at max equal to n+m.
--
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 problem is close than this:
http://uva.onlinejudge.org/external/103/10327.html
I found this:
http://en.wikipedia.org/wiki/Pancake_sorting
Wladimir Araujo Tavares
*Federal University of Ceará
*
On Fri, Feb 11, 2011 at 10:57 AM, juver++ avpostni...@gmail.com wrote:
@jalaj please
@jalaj please ignore my prevoius post, misread the problem.
--
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
@Jalaj: What is the work for each of the operations? I presume that
get is O(1), but don't know if reverse is O(1) or O(end-start).
Dave
On Feb 10, 12:07 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
sort the input array. only following operations on array is allowed:
1)get(index) -gets
Cartesian tree will do.
--
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,
@ dave assume reverse also O(1)
@juver will you elaborate a bit dude
On Thu, Feb 10, 2011 at 8:21 PM, juver++ avpostni...@gmail.com wrote:
Cartesian tree will do.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group,
How do you handle this condition???
1 2 3
2 4 5
3 6 7
3 is smaller than 4~
On Feb 8, 2:48 am, arpit busy in novels
arpitbhatnagarm...@gmail.com wrote:
after a bit analysis i stick strongly to my soln :
0 1 2 3 since element of last row column will
always be
Merge sort with divide and conquer:
suppose n by n array,
Method 1.
1- Get sorted top half and sorted bottom half, (To get sorted top
half and sorted bottom half, recursively using this process)
2- and merge them together.
Time complexity: T(n * n) = 2 * T(n/2 * n) + n * n [until only 2 rows
take 1st as 763 2nd as 753 merge them k[]=76533
take 42 as 1st 42 as 2nd merge as l[] 422
now merge k l as 7654332 add 2 ie
a[00] always lowest
On Tue, Feb 8, 2011 at 5:47 PM, September5th hi.ming...@gmail.com wrote:
How do you handle this
@Jalaj: An efficient algorithm follows:
1. Using a data structure (int value, int row, int col), place the
first column of the array into a minheap. Because the columns are
sorted, the data can simply be copied in order, with row and column
numbers appended; no heap ordering operations will be
as per my analisys
sort elements diagonally in the 2d arry.
we can define diagonals by a[0,i] to a[i,0] is
a[0,i],a[1,i-1],a[2,i-2],.. a[i-1,1],a[i,0], sort the elements
if i col_size then diagonal is a[0,i] is define as
a[0,i],a[1,i-1],a[2,i-2]...a[x,i-x] where
using merge sort takes lot of space complexity.
alternaticely we can solve it using a min- heap
let the array be
0 1 2
0 2 3
1 3 4
then first of all insert top left elemnt in heap(guranteed to be minimum)
heap contans {0}
then and insert elements just greater then i.e to the right and below to
I am not very sure about the correctness of this procedure.
But my approach would be as follows:
Concept: Maintain a set of numbers in which you maintain the values along
with its array indices, such that the next number in the sorted output will
be a part of this set. Consider the set
Just coded the solution, it worked on all the test cases described here in
this thread using the algo i described above :)
The code is available at
https://github.com/algoseeker/Interview/tree/master/sorting
--
You received this message because you are subscribed to the Google Groups
I see a scope of optimization in the algo.
In step 2. Before inserting the element a[i][j], you can make sure that
a[i][j-1] and a[i-1][j] are in the set. If not then do no insert a[i][j] in
the heap. (considering the boundary condition, if j-1 0 or i-1 0 then
assume it is true)
Correct me if I
U using extra space, if you using extra space, simple C++ implementation
will be use a priority queue and do BFS.
On Wed, Feb 9, 2011 at 10:47 AM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote:
@algoseeker
mine approach is also the same but m inserting the elements in a min heap
and you in a
I guess it will fail for the array, looks like incomplete logic.
4 911 14
5 10 13 16
9 16 18 20
On Feb 7, 5:55 pm, Ashish Goel ashg...@gmail.com wrote:
yet to test...
will download xcode to compile, not on linux or windows (:
remote case of all both entries in last row or last
But then we are not using the other property of the array that it's
columns are sorted
On Feb 7, 6:33 pm, jagannath prasad das jpdasi...@gmail.com wrote:
u can merge first two rows and proceed two at time.then slowly merge 4 at a
tym and so on.a recursive algo will do
On Mon, Feb 7,
@ spark , hi
i think either a[0,0] or a[n,n] will be the largest element
we need one more step to test which one is biggest then apply my algo:
I just though we should apply merge sortmean merge 2 array into one )
on 1st row 1st column this will be accurate since rows columns r
Sorted)
Have a look at this earlier discussion where the problem was to find for
array[i], the next nearest larger element than array[i] in the remaining
array.
https://groups.google.com/d/topic/algogeeks/A51KGsPMtAE/discussion
Look at the solution suggested by balaji. Modifying it shall solve your
hey jalaj ,
i just wanna say can be 2 test cases
2 4 8
6 7 9
7 8 10 where a[n,n] is big
or 12 11 10
987
654where a[0,0] is biggest
if u didnt consider increment
can you explain what are you doing ... take this array for example and tell
how are you printing the sorted output
0 1 2 3
2 2 3 4
3 3 4 5
4 5 6 7
On Mon, Feb 7, 2011 at 10:27 PM, arpit busy in novels
arpitbhatnagarm...@gmail.com wrote:
hey jalaj ,
i just wanna say can be 2 test cases
i m taking 1st array as 7 6 5 4 2nd as 7 5 43and merging them
by merge sort so k[]={7,7,6,5,5,4,4,3}
then 1st as 4 3 3 2nd as 4 3 2
l[]=4,4,3,3,3,2
den
m=[2,2,1]
finally merging k , l , m
after a bit analysis i stick strongly to my soln :
0 1 2 3since element of last row column will
always be greater than rest of array
2 2 3 4
3 3 4 5
4 5 6 7 take 7654 as 1st7543 as 2nd merge them
as k[]
array reduced to
0 1 2
2 2 3
3
got a O(n) soln guys
Starts from an empty stack and scan the input array (IN) from the bottom (i
= n-1):
for(int i = n-1; i = 0; i--) {
while (!stack.isEmpty() IN[i] = stack.top()) {
stack.pop();
}
if (stack.isEmpty()) {
OUT[i] = 0;
stack.add(IN[i]);
continue;
}
My method is using DP, as Snehal have pointed out.
Suppose S[0..n-1] and T[0..n-1] denotes the score and time for the n
questions respectively.
C[k][s] denotes the maximum total time when choosing from the first k
questions such that the total score do not exceed s.
Then C[0][s] = 0
Please clarify the problem statement. Provide example.
From the first view problem seems to be unclear.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this
Marks for Questions(1,6): {10,15,20,25,10,20}
Time for Each Questions(1,6) : { 2, 4,3,4, 2,4}
Passing Marks : 40 Out of 100
Find Questions with minimum time to pass the exam?
On Dec 23, 7:04 pm, juver++ avpostni...@gmail.com wrote:
Please clarify the problem statement. Provide example.
From
hint : use dp
On Thu, Dec 23, 2010 at 8:30 PM, Davin dkthar...@googlemail.com wrote:
Marks for Questions(1,6): {10,15,20,25,10,20}
Time for Each Questions(1,6) : { 2, 4,3,4, 2,4}
Passing Marks : 40 Out of 100
Find Questions with minimum time to pass the exam?
On Dec 23, 7:04 pm, juver++
Thanks for reply. I am looking for O(n) for solution.
Davin
On Dec 23, 8:29 pm, snehal jain learner@gmail.com wrote:
hint : use dp
On Thu, Dec 23, 2010 at 8:30 PM, Davin dkthar...@googlemail.com wrote:
Marks for Questions(1,6): {10,15,20,25,10,20}
Time for Each Questions(1,6) :
it is just like 0/1 knapsack problem with maximum weight of knapsack
as 40. but in this case that is minimum that we have to calculate.
calculate marks/time for every element . then try finding the elements
with max value/time to fulfill the quota of marks. i dont know if this
can be done in O(n)
@ankur can you hint your nlogn solution?
On Thu, Dec 23, 2010 at 9:08 PM, Ankur Khurana ankur.kkhur...@gmail.comwrote:
it is just like 0/1 knapsack problem with maximum weight of knapsack
as 40. but in this case that is minimum that we have to calculate.
calculate marks/time for every element
wverything i mentioned above can be done in O(n) but sorting part is
nlogn . so that is what i was saying. can you specify where i was not
clear ?
On Thu, Dec 23, 2010 at 9:22 PM, Nikhil Agarwal
nikhil.bhoja...@gmail.com wrote:
@ankur can you hint your nlogn solution?
On Thu, Dec 23, 2010 at
i will try to elaborate or rewrite tat part
On Thu, Dec 23, 2010 at 10:25 PM, Ankur Khurana
ankur.kkhur...@gmail.com wrote:
wverything i mentioned above can be done in O(n) but sorting part is
nlogn . so that is what i was saying. can you specify where i was not
clear ?
On Thu, Dec 23, 2010
@Ankur Now its clear.:)
On Thu, Dec 23, 2010 at 10:25 PM, Ankur Khurana ankur.kkhur...@gmail.comwrote:
i will try to elaborate or rewrite tat part
On Thu, Dec 23, 2010 at 10:25 PM, Ankur Khurana
ankur.kkhur...@gmail.com wrote:
wverything i mentioned above can be done in O(n) but sorting
@Ankur:
It is just 0/1 knapsack problem:
Choose a subset of the questions with sum of scores not exceeding
(Total Score - Pass Score), while maximize the sum of time of the subset.
So I do not think O(nlogn) greedy algorithm will solve this problem.
On 2010-12-23 23:38, Ankur Khurana
how will you choose that ?? without sorting . can you please mention
what method you intend to use to achieve that purpose ?
On Fri, Dec 24, 2010 at 8:16 AM, Terence technic@gmail.com wrote:
@Ankur:
It is just 0/1 knapsack problem:
Choose a subset of the questions with sum of scores not
sort the array and from the last elements of the array, put element
i(last) in set A and i-1 in set B,
now for the i-2 th element put this element in the set whichever has
lesser sum of elements in both sets and continue this till the least
element
On Dec 22, 7:09 am, Devil Wang
http://anandtechblog.blogspot.com/2010/07/partition-of-array.html
On Wed, Dec 22, 2010 at 7:14 AM, rajessge...@yahoo.com
rajessge...@yahoo.com wrote:
sort the array and from the last elements of the array, put element
i(last) in set A and i-1 in set B,
now for the i-2 th element put this
I think you mean absolute diffrence bewteen two sums is minimal. It's a DP
problem.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
@Kartheek
Ashish algo is perfectly workingBy making before[0]after[length-1]=1
the array is shifted ,which prevents the inclusion of current index.
Ex:
int a[5]={10,4,8,3,9}
before[0]=1
before[1]=10
before[2]=40
before[3]=320
before[4]=960
after[4]=1
after[3]=9
after[2]=27
Thanks for clearing
On Tue, Sep 21, 2010 at 1:58 PM, Naveen Agrawal nav.coo...@gmail.comwrote:
@Kartheek
Ashish algo is perfectly workingBy making before[0]after[length-1]=1
the array is shifted ,which prevents the inclusion of current index.
Ex:
int a[5]={10,4,8,3,9}
It's been discussed here before.
Start by multiplying from either sides of the array and stop when both
pointers reach the opposite side.
takes O(n) time and does not involve division so won't crap out for
cases where some of the elements are 0.
I was asked this for my Google phone screen I wish
I guess before[index] should contain product of the numbers before index and
after[index] should contain all the product after the index but @Ashish algo
isn't that before[index] contains product that includes the number at the
index position also. Please clarify me...
On Sun, Sep 19, 2010 at
To complete the answer, you first need to compute C(m,n) as
wangyanadam1...@gmail.com said and then
look for the closest m to s/2 as sharad kumar said.
proof:
you are looking for two complimentary subset with sum of m and s-m
(assume ms-m)
you are looking for a reachable m, which minimize |m -
This is Balanced Partition problem which can be solved by using
Dynamic Programming, see #7 on this page,
http://people.csail.mit.edu/bdean/6.046/dp/
On Aug 31, 3:12 pm, Raj Jagvanshi raj.jagvan...@gmail.com wrote:
There is an array of some no only 0-9. You have to divide it into two
array
Balanced partition of an array using Dynamic programming
http://codepad.org/2vK13zWb
http://codepad.org/2vK13zWbPS: always add zero to the beginning of the
series to get the proper result.
On Tue, Aug 31, 2010 at 6:49 PM, Jinsong Huang googlegro...@huangus.orgwrote:
This is Balanced Partition
can you please explain more in detail the logic for XORing the index.
On 22.08.2010 07:53, UMarius wrote:
@Nikhil : I considered the array to be a linked list. xoring the
indexes helps when you don't know how many elements you have.
Marius.
On Aug 22, 5:04 am, Nikhil
a={1,2,2,3,4}
b={1,2,3,3,4}
in this case???
elements are not equal but they certainly consist equal set of
integers(1,2,3,4) which is what question says.
On Sun, Aug 22, 2010 at 7:53 AM, UMarius mar...@aseara.ro wrote:
@Nikhil : I considered the array to be a linked list. xoring the
indexes
Its easier to look at a property of numbers. It will be interesting to
evaluate/prove if two different arrays have same value for sum of elements
and sum of squares of the elements.
On Fri, Aug 20, 2010 at 9:38 AM, Nikhil Agarwal
nikhil.bhoja...@gmail.comwrote:
Check this new algo: plz provide
@Nikhil Agarwal: You cannot take extra memory and neither the range of
numbers is specified.
Counting will not be a viable option.
On Fri, Aug 20, 2010 at 9:38 AM, Nikhil Agarwal
nikhil.bhoja...@gmail.comwrote:
Check this new algo: plz provide counter eg.(if any)
step 1 : count the no. of
What about this?
1. xor all elements of each array and their corresponding indexes
sum all the elements of each array mul all elements of each array
2. if all results are the same then the arrays are identical
Nice to meet you all, I just joined and this is my first post :) ...
Given two
@UMarius: A = {1,2}, B = {2,1} fails your test. If you reread the
original problem, you see that the question is not whether the arrays
are identical (which is easily determined by simply comparing them
element-by-element in O(n)), but whether they contain the same values,
possibly in a different
@marius Why are you xorring the indexes along with nos.?any special reason?
On Sun, Aug 22, 2010 at 7:19 AM, UMarius mar...@aseara.ro wrote:
@Dave: I read the question correctly and for A = { 1 , 2} B = { 2 , 1}
the output is correct.
Maybe I didn't explain the steps correctly. This is the
@Nikhil : I considered the array to be a linked list. xoring the
indexes helps when you don't know how many elements you have.
Marius.
On Aug 22, 5:04 am, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote:
@marius Why are you xorring the indexes along with nos.?any special reason?
On
@Nikhil: A = {0,2,2}, B = {0,0,4}.
Rather than challenging everyone to keep coming up with
counterexamples, please provide a rationale as to why an algorithm
such as this should work. It looks as if you have two equations in 2N
unknowns and are trying to assert that the only solution is A_1 =
Nikhil's algo is correct if the following is always true:
Given: x + y = S, x * y = M
and x' + y' = S', x' * y' = M'
If: S' = S and M' = M, then x = x' and y = y'
i.e for given sum and product, the elements are unique.
On Thu, Aug 19, 2010 at 12:54 PM, Nikhil Agarwal
@Nikhil Jindal: What you say is true for 2 numbers, but not for more
than 2.
1 + 6 + 6 = 2 + 2 + 9 = 13, and 1 * 6 * 6 = 2 * 2 * 9 = 36.
Dave
On Aug 19, 6:00 am, Nikhil Jindal fundoon...@yahoo.co.in wrote:
Nikhil's algo is correct if the following is always true:
Given: x + y = S, x * y = M
1. Add sum of squares of all numbers in respective groups, if equal
goto step 2.
2. XOR all elements of both groups, (if==0) elements are same.
On Aug 19, 9:21 pm, Dave dave_and_da...@juno.com wrote:
@Nikhil Jindal: What you say is true for 2 numbers, but not for more
than 2.
1 + 6 + 6 = 2 + 2
@Saikat: Rather than challenging everyone to keep coming up with
counterexamples, please provide a rationale as to why an algorithm
such as this should work. It looks as if you have two equations in 2N
unknowns and are trying to assert that the only solution is A_1 =
B_1,
A_2 = B_2, etc. (where I
@saikat ur algo fails with the test case a1=-2,-2 and a2=2,2
On Thu, Aug 19, 2010 at 10:22 PM, Saikat Debnath saikat@gmail.comwrote:
1. Add sum of squares of all numbers in respective groups, if equal
goto step 2.
2. XOR all elements of both groups, (if==0) elements are same.
On Aug 19,
@Chonku, Your algorithm seems to fail on A = {0,1,-1), B = (0,2,-2).
Dave
On Aug 18, 7:52 am, Chonku cho...@gmail.com wrote:
1. Sum all the elements of both arrays. If the sum are same then perform
step 2. If the sum is not different, then arrays are different.
2. Xor elements of first array
@Srinivas, Your algorithm seems to fail on A = {0,1,-1), B =
(0,2,-2).
Dave
On Aug 18, 10:53 pm, srinivas reddy srinivaseev...@gmail.com wrote:
add one more thing to the solution suggested by nikhil i.e;count the number
of elements in array 1 and number of elements in array2 if these two
@Chonku, Make that: Your algorithm seems to fail on A = {0,1,-2), B =
(0,2,-3). I was thinking onwa-complement arithmetic instead of twos-
complement.
Dave
On Aug 18, 11:57 pm, Dave dave_and_da...@juno.com wrote:
@Chonku, Your algorithm seems to fail on A = {0,1,-1), B = (0,2,-2).
Dave
On
@Srinivas, Make that: Your algorithm seems to fail on A = {0,1,-2), B
=
(0,2,-3). I was thinking ones-complement arithmetic instead of twos-
complement.
Dave
On Aug 18, 11:59 pm, Dave dave_and_da...@juno.com wrote:
@Srinivas, Your algorithm seems to fail on A = {0,1,-1), B =
(0,2,-2).
Dave
@dave
akash said
Can you please tell me why you chose a bst, simply traversing the array and
incrementing the count would
have also worked in this case and it would have been O(n).
so .. if the range will be high suppose there r few numbers which are very
large so taking an auxillary array and
check for 1st element if it occurs n times
if not check for last element if it occurs n times
if not move a block of 3
On Sat, Jul 3, 2010 at 3:38 AM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote:
@dave
akash said
Can you please tell me why you chose a bst, simply traversing the array
@ dave its not always that the number be adjacent as the array is not sorted
suppose array is 2 1 3 4 2
On Fri, Jul 2, 2010 at 6:04 PM, Dave dave_and_da...@juno.com wrote:
For problem 1, finding a number that is repeated just once is enough.
Scan the array to see if there are two adjacent
@Jalaj. You apparently missed the sentence Otherwise, look for the
repeat in the first 5 numbers.
Dave
On Jul 2, 7:42 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
@ dave its not always that the number be adjacent as the array is not sorted
suppose array is 2 1 3 4 2
On Fri, Jul 2,
@Saurabh. Checking three adjacent numbers won't work, as the example
1,2,3,4,1 shows.
You apparently missed the sentence, Otherwise, look for the repeat in
the first 5 numbers. If you don't find two equal adjacent numbers,
then there will be a repeat within the first five numbers. How do you
know
for count suppose if there are very big numbers ..then space will nt be
efficient
On Fri, Jul 2, 2010 at 7:05 PM, saurabh gupta sgup...@gmail.com wrote:
@Dave,
for 2n+1 you can have a configuration where repeated nos may not be
adjacent
you need a block of 3 instead of 2.
On Fri, Jul 2,
@Jalaj. I don't understand how your comment contributes to the
discussion. Please explain.
Dave
On Jul 2, 10:56 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
for count suppose if there are very big numbers ..then space will nt be
efficient
On Fri, Jul 2, 2010 at 7:05 PM, saurabh
@Dave:
ah, yeah, you are right
On Fri, Jul 2, 2010 at 11:13 PM, Dave dave_and_da...@juno.com wrote:
@Jalaj. I don't understand how your comment contributes to the
discussion. Please explain.
Dave
On Jul 2, 10:56 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
for count suppose if
It would be great if they have the likes and dislike like in yahoo
answers so that correct or rather best solutions can be looked at
immediately then subsequently the other solutions!!
second, if u cud give the link to the problem, even we can try the
problem and submit it and gain some confidence
i meant make an array of indexes.. index[]={0,1...,n-1}
now sort the original array and move the elements of index array
accordingly..
now follow modelling expert's algo nd while taking largest-smallest check if
the index of largest in index array index of smallest in index array.
On 13 June
@BALARUKESH
i think the problem is to maximize the diffrence j-i according to condition
and in your solution j can be less than i.
This problem can be solved by sorting the array first, then taking
diffrence.
this solution is done in O(nlogn).
--
You received this message because you are
Problme is not clear.
Quesrtions:
1. Is the array all of positive numbers
if yes then sort the array in ascending order. Now for every j, ji
and i,j =n, A[j]A[i] and so A[j]-A[i] 0. Now if we want max(j-i)
such that A[j]-A[i]0, it has to be j=n, the last element of A and
i=1, the first element of
Let's say array A , 1 till n
s_index = 1; e_index = n ;
start = A[s_index] ;
end = A[e_index];
result = 0; //! j - i
if ( *end *start ){
result = index(end) - index(start) ( only of its greater than
previous value of result )
break ;
}else{
end-- ; //! till
i think we need to maintain an array of index as well such that while
subtracting smallest element from largest element of sorted array we need to
check if index of largest is greater than index of smallest. if no..then
this is not the solution..
On 12 June 2010 14:20, Modeling Expert
yes we need to maintain an array that shows the real indexes before sorting
and then loop on the elements and find the minimum index that appeared
before a number in the sorted array and subtract it from it's index
and find the maximum difference
On 6/12/10, divya jain sweetdivya@gmail.com
This problem seems to be finding the maxdiff in an array.
int maxdiff ( int A[], int n ) {
// write your code here
int max_diff = A[1] - A[0];
int min_element = A[0];
int i;
for(i = 1; i n; i++)
{
if(A[i] - min_element max_diff)
max_diff = A[i] - min_element;
if(A[i]
@sourav : if I understood problem correctly , you can't change the
list ( hence you can't sort ).
and list can containt + . - ive ints .
e.g. say list is
7 9 1 -4 8 0 0 0 3 1 0
Here answer is index(0) - index(-4) = 11
@divya : didn't get what you said , but guess you also thought of
sorting
@Satya: I don't think what you have coded will work.. though i have not read
the whole code.
Don't you think a simple divide and conquer scheme would work...(almost like
the mergesort)
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer
How will it be 12 12 5 6 6?? I can understand that the first number in
the list is place first so
it could be 12 12 6 6 5. How will it be 12 12 5 6 6?
On Jun 6, 7:47 am, divya jain sweetdivya@gmail.com wrote:
output willl be 12 12 5 6 6
On 6 June 2010 18:27, souravsain souravs...@gmail.com
@Anand: Your solution will take huge space and can easily be made to
run out of memory!
If arr5[] = {12,12,6,6,635}, you will run into n^3 space complexity.
For arr[5]={12,12,6,6,390625} it will be n^6.
Sain
On Jun 7, 3:27 am, Anand anandut2...@gmail.com wrote:
Here is my approch which runs in
101 - 200 of 234 matches
Mail list logo
