Counting sort does not run in O(1) space though. Optimally it will run in
O(K) space, where A is an array of integer numbers and K = max(A) - min(A)
On Saturday, February 9, 2013 9:52:01 PM UTC-5, Mohanabalan wrote:
can use counting sort
On Sun, Jul 15, 2012 at 6:37 PM, santosh thota
A bit vector is basically just a sequence of bits such as a word or even an
array of words. Here is an example...
int x = 5; // 32 bit word size on Intel IA-32 Architecture In C
programming language.
A variable in C will be either located in a register in memory or in Main
Memory. You
This will only work if each element in the array are relatively prime to
one another, that is for any two elements x, y in array A the gcd(x,y) = 1,
which is also just another way of saying no number divides another number
in the array. Once this rule is broken, then
the algorithm will no
use XOR
On Tue, Apr 30, 2013 at 6:12 AM, Gary Drocella gdroc...@gmail.com wrote:
This will only work if each element in the array are relatively prime to
one another, that is for any two elements x, y in array A the gcd(x,y) = 1,
which is also just another way of saying no number divides
:O the final required sum would be 4C0 * a5 - 4C1 * a4 + 4C2 * a3 - 4C3 *
a2 + a1 how ? , did i missed something id yes can you paste the link or
explain ?
Thanks
Shashank
On Wednesday, April 10, 2013 5:09:41 AM UTC+5:30, Shachindra A C wrote:
Consider n = 5. Naming the array elements as
in this Problem if the array is
A[n] = {a0,a1,a(n-1),a(n)}
after the second iteration,
the value will be
{a0 -2*a2+a3, a2 -2*a3 + a4, a3-2*a4+a5,, a(n-2)-2a(n-1)+a(n)}
if we add all these terms then
all the middle elements will be canceled out so the remaining will be.
{a0-a2 -
On 4/13/13 10:05 PM, pankaj joshi wrote:
in this Problem if the array is
A[n] = {a0,a1,a(n-1),a(n)}
after the second iteration,
the value will be
{a0 -2*a2+a3, a2 -2*a3 + a4, a3-2*a4+a5,, a(n-2)-2a(n-1)+a(n)}
if we add all these terms then
all the middle elements will be canceled
It is O(N^2) because the inner loop takes N steps to execute and that
loop will be executed N times.
However, I would suggest not using recursion. There is no reason to
not do it iteratively. Your recursive solution has no base case so it
will recurse until your computer runs out of stack space,
i forgot to add base case..can add wen 2 elemnts are there then there sum
is stored and we reurn from there...i m in hurry,,,sry for that,,
On Wed, Apr 10, 2013 at 12:11 AM, Don dondod...@gmail.com wrote:
It is O(N^2) because the inner loop takes N steps to execute and that
loop will be
If you have any other solution ..please post that...i thnik recursion is ok
with base case...we need to scan again after first iteration...??
On Wed, Apr 10, 2013 at 12:12 AM, rahul sharma rahul23111...@gmail.comwrote:
i forgot to add base case..can add wen 2 elemnts are there then there sum
int getsum(int *a, int n)
{
while(--n)
{
for(int i = 0; i n; ++i)
a[i] = a[i+1] - a[i];
}
return a[0];
}
I'm not really clear about how it is intended to work. It seems that
if you start with an array of N values, each iteration reduces the
number of values by 1, so
Recursion and iteration don't differ in this algorithm. But avoid using
recursion if same can be done using iteration. In practical cases, system
does not allow very large depth in recursion. So for large values of n,
there can occur segmentation fault.
On Tue, Apr 9, 2013 at 11:43 AM, rahul
Consider n = 5. Naming the array elements as a1,a2,a3,a4,a5 , the final
required sum would be 4C0 * a5 - 4C1 * a4 + 4C2 * a3 - 4C3 * a2 + a1.
That is nothing but the pattern of a binomial expansion. Using this method,
the complexity can be reduced to O(n).
Correct me if I'm wrong!
On Tue, Apr
On 4/10/13 12:13 AM, rahul sharma wrote:
If you have any other solution ..please post that...i thnik recursion
is ok with base case...we need to scan again after first iteration...??
First of all, the array size and number of iteration both won't be N or
else the answer will always be 0.
I take
hi sourab please explain what bit vector1 and bit vector 2 really are can
you give an example please?
On Saturday, February 16, 2013 11:20:59 PM UTC+5:30, sourabh wrote:
you can solve this problem using bitvector/bitset.
first scan :
scan the array set the bit on odd occurrence and unset on
@sandeep he is talking about constant space.
On Tue, Mar 19, 2013 at 5:31 PM, sandeep kumar
sandeepkumar1...@gmail.comwrote:
Hey what if while scanning through the array we create a BST n check
simultaneously that :
current node == current node's parent current node == current node's
left
Hey what if while scanning through the array we create a BST n check
simultaneously that :
current node == current node's parent current node == current node's
left or right child
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To
Yes, thats a valid point Don.
Thats what i meant when i wrote //is that correct? in the comments on
the array line in code.
int a[] = {2,2,3,3,3,1,1,4,4}; // is this correct?
On Wed, Feb 13, 2013 at 9:09 PM, Don dondod...@gmail.com wrote:
The xor approach only works if there are no values
you can solve this problem using bitvector/bitset.
first scan :
scan the array set the bit on odd occurrence and unset on even or
0 occurrence.
second scan :
shift all the odd occurring elements in beginning of array and even towards
end.
third scan : till end of odd occurring elements.
take
Sachin Chitale,
Dude the xoring operation will give us xor of numbers with freq 1 and 3
respectively. How do you filter out the number with the frequency 3??
On Tuesday, February 12, 2013 11:44:08 PM UTC+5:30, Sachin Chitale wrote:
use ex-or operation for all array elements..
a^a=0
a^a^a=a
Search for BitSet/BitVector in java .
On Tue, Feb 12, 2013 at 11:44 PM, Sachin Chitale
sachinchital...@gmail.comwrote:
use ex-or operation for all array elements..
a^a=0
a^a^a=a
On Sun, Feb 10, 2013 at 8:22 AM, Mohanabalan D B
mohanabala...@gmail.comwrote:
can use counting sort
On
@Sachin Chitale : Very good approach dude .
thumbs up +1
--
Arun Singh Chauhan
Engineer (RnD 2), Samsung Electronics
Software Engineering Lab, Noida
On Tuesday, February 12, 2013 11:44:08 PM UTC+5:30, Sachin Chitale wrote:
use ex-or operation for all array elements..
a^a=0
a^a^a=a
On
The xor approach only works if there are no values which occur only
once. But the problem statement indicates that some numbers occur
once, some occur twice, and one occurs three times. So you will end up
with prod equal to the xor of all of the values which occur once or
three times. Put that in
can use counting sort
On Sun, Jul 15, 2012 at 6:37 PM, santosh thota santoshthot...@gmail.comwrote:
If we can retrieve ith prime efficiently, we can do the following...
1.maintain a prod=1, start from 1st element, say a[0]=n find n th prime
2.check if (prod% (ith_prime * ith_prime )==0) then
@anurag : there is no need to SORT. as it will increase complexity O(n) to
O(n log n).
here is the correct code.. please look over it and notify me if i'm wrong .
T.C. = O( n )
// ex: 1 4 3 2 0 i'm explaining on behalf of it.
bool permute (int *arr , int N )
{
if ( N=1 ) return false;
Can anyone give me some idea if the given no is small like 12 then the next
one is 17
On Mon, Dec 24, 2012 at 7:56 PM, marti amritsa...@gmail.com wrote:
I REPEAT, THERE is no need to SORT;
http://en.wikipedia.org/wiki/Permutation#Lexicographical%5Forder%5Fgeneration
On Friday,
Hi Ritesh
Yeah, you are right. we do not need to sort. my bad
Thank you for explaining clearly
On Thu, Dec 27, 2012 at 4:29 AM, Ritesh Mishra rforr...@gmail.com wrote:
@anurag : there is no need to SORT. as it will increase complexity O(n) to
O(n log n).
here is the correct code.. please
I REPEAT, THERE is no need to SORT;
http://en.wikipedia.org/wiki/Permutation#Lexicographical%5Forder%5Fgeneration
On Friday, December 14, 2012 11:56:16 AM UTC+5:30, tapan rathi wrote:
For a given number, find the next greatest number which is just greater
than previous one and made up of
@marti
your answer is completely wrong (check for 234987156221 ans is 2349871*61225
* whereas your answer would be 2349871*65225*)
and we do need to sort
On Mon, Dec 17, 2012 at 9:10 AM, marti amritsa...@gmail.com wrote:
Yeah thanks Sandeep, theres an error in example...it should be
Here is what you do
EG: 5436782
ans is 5436872
how did we arrive?
FInd least index i, such that a[i-1] = a[i] starting from rigthmost
5436782
(8)
Now , Find least index j such that a[j-1] = a[i-1]:
5436782
(7)
swap them
= 5436872
Now swap all values between i and j.
hello all... anwer to previous example would be 5436827 instead of
5436872please correct it :)
On Sun, Dec 16, 2012 at 11:48 PM, marti amritsa...@gmail.com wrote:
Here is what you do
EG: 5436782
ans is 5436872
how did we arrive?
FInd least index i, such that a[i-1] = a[i] starting from
Let the number is stored in an array a[n] with MSB at index 0...
1. i = n-1;
reduce i till a[i]=a[i-1] i 0.
If here i =0 means give number is largest possible number made out of digits
otherwise i is pointing to a digit such that a[i]a[i+1]
2. find smallest digit from a[i+1 to n-1] just
Yeah thanks Sandeep, theres an error in example...it should be
5436827.However there is no need to sort.
On Friday, December 14, 2012 11:56:16 AM UTC+5:30, tapan rathi wrote:
For a given number, find the next greatest number which is just greater
than previous one and made up of same digits.
For the series like 2,4,3,9,4,16,5,25 ur algo runs in o(n*n/2) =o(n^2)
On Friday, 13 July 2012 13:16:50 UTC+5:30, jatin wrote:
1)Find product of the array and store it in say prod o(n) and o(1)
2)now traverse the array and check if
static int i;
tag:
while(in)
if( prod
If we can retrieve ith prime efficiently, we can do the following...
1.maintain a prod=1, start from 1st element, say a[0]=n find n th prime
2.check if (prod% (ith_prime * ith_prime )==0) then return i;
else prod=prod*ith_prime;
3.repeat it till end
On Thursday, 12 July 2012 10:55:02
.
Plus this will exceed O(n) in the worst case, as we may keep visiting
the goto again and again. Not sure of its exact time complexity.
--
From: vindhya chhabra
Sent: 13-07-2012 17:46
To: algogeeks@googlegroups.com
Subject: Re: [algogeeks] Re: Amazon Interview
Or we can make a BST from array list in o(n)
then traverse it inorder-o(logn)
but this solution requires o(logn) space though.
On Friday, 13 July 2012 13:16:50 UTC+5:30, jatin sethi wrote:
1)Find product of the array and store it in say prod o(n) and o(1)
2)now traverse the
@jatin:
Your first method may be proved wrong.
Here is a counter test case:
Suppose the array is:
27 729 19683 2 3 3 27 3 81 729
Here, 81 occurs once, 19683 occurs once, 2 occurs once,729 occurs twice, 27
occurs twice, and 3 occurs thrice.
You are supposed to return 3
But as per your method,
@adarsh
But i think jatin has asked to check for the number( we achieved in step 1)
occuring thrice or not..and in this check 27 will rule out.but i doubt the
algo given by Jatin runs in O(n) time. please comment.
On Fri, Jul 13, 2012 at 5:17 PM, adarsh kumar algog...@gmail.com wrote:
@jatin:
To: algogeeks@googlegroups.com
Subject: Re: [algogeeks] Re: Amazon Interview Question
@adarsh
But i think jatin has asked to check for the number( we achieved in step 1)
occuring thrice or not..and in this check 27 will rule out.but i doubt the
algo given by Jatin runs in O(n) time. please comment.
On Fri
@googlegroups.com
Subject: Re: [algogeeks] Re: Amazon Interview Question
@adarsh
But i think jatin has asked to check for the number( we achieved in step
1) occuring thrice or not..and in this check 27 will rule out.but i doubt
the algo given by Jatin runs in O(n) time. please comment.
On Fri
exact time complexity.
--
From: vindhya chhabra
Sent: 13-07-2012 17:46
To: algogeeks@googlegroups.com
Subject: Re: [algogeeks] Re: Amazon Interview Question
@adarsh
But i think jatin has asked to check for the number( we achieved in step
1) occuring thrice
chhabra
Sent: 13-07-2012 17:46
To: algogeeks@googlegroups.com
Subject: Re: [algogeeks] Re: Amazon Interview Question
@adarsh
But i think jatin has asked to check for the number( we achieved in step
1) occuring thrice or not..and in this check 27 will rule out.but i doubt
the algo given by Jatin
: 13-07-2012 17:46
To: algogeeks@googlegroups.com
Subject: Re: [algogeeks] Re: Amazon Interview Question
@adarsh
But i think jatin has asked to check for the number( we achieved in step
1) occuring thrice or not..and in this check 27 will rule out.but i doubt
the algo given by Jatin runs in O
+1.
--
From: Shruti Gupta
Sent: 14-07-2012 08:08
To: algogeeks@googlegroups.com
Subject: Re: [algogeeks] Re: Amazon Interview Question
@jatin: even i think it will b more than O(n).. infact it will be
O(n-square) in the worst case as if each hit is spurious(until
@Algo bard: No. You can do an O(n) time, O(n) space solution with a radix
sort, or you can do an O(n log n) time, O(1) space solution with a variety
of sorts.
Dave
On Thursday, July 12, 2012 12:25:02 AM UTC-5, algo bard wrote:
Given an array of integers where some numbers repeat once, some
If the assumption is that there is only one element which occurs
once , some elements repeat twice and only one element which repeats
thrice
then following is the code according to the assumption made
http://ideone.com/yseYy
--
You received this message because you are subscribed to the
could u explain how would you use a trie for this??
On Thursday, June 14, 2012 1:01:00 PM UTC+5:30, Mohit Rathi wrote:
Hi,
*There are two arrays of length 100 each. Each of these has initially n
(n=100)
elements. First array contains names and the second array contains numbers
such that
Store each of the words in array in a trie and mark the end of the word by
its corresponding entry in the second array. Now if u are searching for a
word it'll take O(length of word) if there is a mismatch at any point you
know the word is not present in array1 and add it to the trie or else
You can use a trie with end of word marked by its corresponding entry in
array.
On Thursday, 14 June 2012 13:01:00 UTC+5:30, Mohit Rathi wrote:
Hi,
*There are two arrays of length 100 each. Each of these has initially n
(n=100)
elements. First array contains names and the second array
+1 for trie..
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/
On Fri, Jun 15, 2012 at 5:21 PM, enchantress
I think adjacency list can be implemented by vector of vector.
vector vectorint Nodes;
The size of vector Nodes is total no of nodes.
Every element of the vector will store all its adjacent edges.
Nodes[i] is a vector containing all the edges adjacent to node i.
So, we can copy the graph easily.
Here, can we use function for comparison ??
--
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/-/ZgGYGAZwvcoJ.
To post to this group, send email to
Please reply with your alog...!
--
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/-/OGVCUV_hutUJ.
To post to this group, send email to
Hi Guys,
The @pacific solution is the best?
Wladimir Araujo Tavares
*Federal University of Ceará
*
On Tue, Jun 28, 2011 at 7:26 AM, sunny agrawal sunny816.i...@gmail.comwrote:
you can initialize it to (Max-Min+1)
where Max = max of all elements
Min = min of all elements
Or simple
what will be the oldDiff initially. can u plz explain with a egsample
--
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/-/NXQqyUTbdlkJ.
To post to this group,
you can initialize it to (Max-Min+1)
where Max = max of all elements
Min = min of all elements
Or simple initialise it to a large integer like 0x7fff for 32 bit
numbers.
On Tue, Jun 28, 2011 at 3:32 PM, vikas mehta...@gmail.com wrote:
what will be the oldDiff initially. can u plz explain
@pacific you are perfectly right but the order is not o(kn) its is
O(k*n*log(n)) because to get the least number u have to use priority queue
nd at every iteration (from 1 to k*n) u have to push and pop one single
element.
--
Anshuman Mishra
IIIT Allahabad
-
My approach :
Have a pointer to the start (smallest of the array) of each of the N
arrays.
Until all pointers reach end of respective arrays :
take the smallest value from all of the pointers
and compute the difference between the smallest and the current pointers
of each of the arrays
see here let me know if anything wrong..??
http://shashank7s.blogspot.com/2011/05/wap-to-find-minimum-difference-between.html
Thanks Regrads
Shashank the Best Way to Escape From The problem is to Solve it
Computer Science Engg.
BIT Mesra
--
You received this message because you are
For an O(n) in place : http://arxiv.org/pdf/0805.1598
There are links to other algo's for the same problem with varying
degrees of difficulty. I think it would be a very high expectation
indeed, if they expected this solution from the interviewee.
On Feb 28, 9:27 pm, Vinay Pandey
I forgot to mention
Time complexity: O(n), Space complexity: O(1)
Assuming you accept my solution :-)
On Mon, Feb 28, 2011 at 9:27 PM, Vinay Pandey babbupan...@gmail.com wrote:
Hi,
Here is my solution, let me know:
/* a helper function */
void swap(int* arr, int index1, int index2) {
/*
Here is one recursive solution I propose :
consider example a1,a2,a3,a4,b1,b2,b3,b4
1. if n is even
swap second Half of first array with first half of second array
so it would be a1,a2,b1,b2,a3,a4,b3,b4
and it can be solved recursively
so rearrange({a1,a2,a3,a4,b1,b2,b3,b4}) =
Hi,
Here is my solution, let me know:
/* a helper function */
void swap(int* arr, int index1, int index2) {
/* this is only to swap to integers */
arr[index1] = arr[index1]^arr[index2];
arr[index2] = arr[index1]^arr[index2];
arr[index1] = arr[index1]^arr[index2];
}
/* Actual switching */
void
@gaurav. They way I see it it's O(nlogn)?
you have n/4 for each level of the recursion tree and logn height. In
total its O(nlogn)
On Feb 28, 9:27 pm, Vinay Pandey babbupan...@gmail.com wrote:
Hi,
Here is my solution, let me know:
/* a helper function */
void swap(int* arr, int index1,
@jalaj U needs to clarify becoz what i can say that dat is overwritten
in ur explanation so we loosing the original data where we are saving
when we swapping the elements ur explanation seems to be right but
little confusing
@ujjwal i haven't tested ur code but i think its O(n^2) then why not
Are there any constraints in the problem, because it seems straight forward.
if number of elements are 2n indexed from 0 to 2n-1
for i=0 to n-1:
new_array[i*2]=old_array[i];
new_array[i*2+1]=old_array[i+n];
On Mon, Feb 28, 2011 at 7:41 PM, bittu shashank7andr...@gmail.com wrote:
@jalaj
how abt dis guys ??
#include stdio.h
#include string.h
#define MAX 100
int main()
{
int n;
int i;
int j;
int it;
char input[MAX];
char tmp;
scanf(%s,input);
n = strlen(input);
i = j = n/2;
for(it=1; itn-2; it++) {
if(it%2 == 1) {
@arpit otherwise it wont b amzon quest..
space dude..space is constants
Thanks
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
well space complexity should be mentioned in the question then, anyway,
start with the second element put it at its correct location(say x), then
take x put it at its correct location, this was when you do this n-1 time,
you will get the correct answer because it forms a cycle.
On Mon, Feb 28,
@Arpit: The problem is that for certain values of n, you get more than
one cycle, and the cycles are disjoint. You have to find all of the
disjoint cycles and move the elements in each one.
Dave
On Feb 28, 12:25 pm, Arpit Sood soodfi...@gmail.com wrote:
well space complexity should be mentioned
updated :)
Given a boolean matrix with all the true elements on left side in the row so
that each row can be broken into two parts left part containing only true
elements and right part containing only false elements. Find the row with
max number of true elements in it.
00011
0
1
O(m+n).
Search from rightmost top corner. Count the no of zero from right and go to
left, i.e. traverse through columns from right of the first row. When you
find a column having 0, go down to lower row. Check the correspondent column
is 1 or not. If it is, follow the above step or else go down to
@SoumyaNice Solution.
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options,
@shiva , U didn't check for the cycles.Since in question it is never
mentioned about cycles u can add few steps to check cycles.
(eg)
1 3 - 5
| |
| |
| |
4-3--3
--
You received this message because you are subscribed to the Google Groups
Algorithm
oh thank u :)
On Dec 22, 11:20 am, bittu shashank7andr...@gmail.com wrote:
Xcellent Shiva..keep goin on..\
Best Regards
Shashank Mani Narayan
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
ya through down pointer we can print..coz each time i m making fwd as
NULL
On Dec 20, 2:33 pm, Rishi Agrawal rishi.b.agra...@gmail.com wrote:
See inline ..
On Sat, Dec 18, 2010 at 12:09 PM, siva viknesh sivavikne...@gmail.comwrote:
Given a linked list structure where every node
Xcellent Shiva..keep goin on..\
Best Regards
Shashank Mani Narayan
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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
It can be done easily by counting sort
On Wed, Dec 15, 2010 at 5:36 AM, Soumya Prasad Ukil
ukil.sou...@gmail.comwrote:
Have a look : http://geeksforgeeks.org/?p=1488
On 15 December 2010 05:19, Saurabh Koar saurabhkoar...@gmail.com wrote:
@ Bittu:
Lets analyze your code with
use a dictionary (available in C#... basically a collection of generic
key-value pairs where the key lookup is O(1) - hashed internally)
since number that occurred first should be listed first when
frequencies are the same, u need to record the first occurrence of
each number as well. Hence, the
@ankur,saurabh,soumya..
ya ankur i forget to remove range from dare also no need to find
range for this..\
put size-1 intead of range so that malloc will alocate the memory to
all elements in array ..no hope its fine...
what i did is that
i took counter array thta cvontains the no of
Have a look : http://geeksforgeeks.org/?p=1488
On 15 December 2010 05:19, Saurabh Koar saurabhkoar...@gmail.com wrote:
@ Bittu:
Lets analyze your code with iterations:
the array contains 1 3 3 1 2 3 5 2 3
count contains 0 2 2 4 0 1 0 0 0
now 1st iteration:
i=8,7,6 the inner loop
you can use hash table for this dude.
On Dec 14, 8:22 pm, Prims topcode...@gmail.com wrote:
given some positive numbers
output the numbers in decreasing order of frequency..in case of a tie
print the number which occurred first
for eg: 1,3,3,1,2,3,5,2,3
the output should be 11225
--
@sajj: if the range of number is not given then ?
On Tue, Dec 14, 2010 at 11:41 PM, sajj sajjv...@gmail.com wrote:
you can use hash table for this dude.
On Dec 14, 8:22 pm, Prims topcode...@gmail.com wrote:
given some positive numbers
output the numbers in decreasing order of frequency..in
what you can do is create a vector pairint,int and sort it on the
baisis of secondary key where it will be it's frequency. if tha range
is not given. If the range is in permissible limits, then hash table
is the answer. I suppose.
On Tue, Dec 14, 2010 at 11:45 PM, Ankur Khurana
#include stdlib.h
#includestdio.h
#includeconio.h
int main()
{
int array[]={1,3,3,1,2,3,5,2,3};
int size=sizeof(array)/sizeof(int);
int min,max;
max=min=array[0];
int i=0;
for(i = 1; i size; i++)
{
if (array[i] min)
min = array[i];
else if (array[i] max)
bittu, in stead of writing your code, put your logic here. It is not the
place to show how capable one is to write a program.
On 14 December 2010 11:00, bittu shashank7andr...@gmail.com wrote:
#include stdlib.h
#includestdio.h
#includeconio.h
int main()
{
int
I think ankur khanna's solution is appropriate. couldn't get what bittu was
trying to do completely.. could you just explain it once please!
On Wed, Dec 15, 2010 at 10:35 AM, Soumya Prasad Ukil
ukil.sou...@gmail.comwrote:
bittu, in stead of writing your code, put your logic here. It is not the
@gene: can you do dry run a test case:
a[0]-a[n-1]
0 1 2 31 34 135
and if u c
On Tue, Dec 7, 2010 at 8:55 AM, Gene gene.ress...@gmail.com wrote:
I should have mentioned that this problem only makes sense if the
array values must be unique.
On Dec 6, 8:20 pm, Gene gene.ress...@gmail.com
@Divesh I have updated my algo and Array A[1,2,3.n] is sorted with
unique elements.CALL FIND_EQUAL(A,1,n)
int FIND_EQUAL(A,start,end)
1.Go to the middle element
2. If A[mid]mid)
3. if(start==mid)
4 return mid-1;
5return FIND_EQUAL(A,1,mid-1);
6 if(A[mid]=mid)
7
You guys are working too hard. Think about the sequence of numbers
[ A[i] - i | i = 0,1,2,...n-1 ]. You are trying to probe this
sequence to find the number of zeros. If you think about it for a
while, you will see that this sequence is non-decreasing. It must be
a segment of zero or more
I should have mentioned that this problem only makes sense if the
array values must be unique.
On Dec 6, 8:20 pm, Gene gene.ress...@gmail.com wrote:
You guys are working too hard. Think about the sequence of numbers
[ A[i] - i | i = 0,1,2,...n-1 ]. You are trying to probe this
sequence to
If All the elements are unique and sorted in ascending order then we can
design an algorithm for O(lgn) and all nos are positive.
Run FIND_EQUAL(A,0,N-1) [A0,A1 and A2 are the array elements]
FIND_EQUAL(A,start,end)
1.Go to the middle element
2.If A[mid]==mid)
return mid+1;
if(A[mid]mid)
yaar I can use simple O(n) sweep to find out who all are equal, I think it
can't be less than this
On Sat, Dec 4, 2010 at 8:05 PM, Abioy Sun abioy@gmail.com wrote:
2010/12/4 ankit sablok ankit4...@gmail.com:
as all the elements are sorted in the array make a min heap of the
array
@Nikhil
run you algo ..
on test case
index - 1 2 3 4 5
value - 1 2 3 4 5
ouput is mid+1= 3+1=4
but it should be 5...
correct me if i am wrong... and u have assumed all are positive, hence base
index should be 1
On Sun, Dec 5, 2010 at 4:41 PM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote:
If
@ashim please refer my post.I posted an o(lgn) algo.i.e. I am copying again
below with an update
If All the elements are unique and sorted in ascending order then we can
design an algorithm for O(lgn) and all nos are positive.
Run FIND_EQUAL(A,0,N-1) [A0,A1 and A2 are the array elements]
2010/12/5 juver++ avpostni...@gmail.com:
Wrong.
Counterexample: 1 2 2 2 2 6
suppose you mean 1 3 3 3 3 6?
1) divide-conquer
2) search binary, in each sub array [s, t],
mid = (s+t)/2
if t array[mid]:
// no need to check the part after mid, all will fail
else if s array[mid]:
// no need
Finding the longest increasing sub sequence and comparing with the
original array ...will this method work?
--
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
ya exactly..dp solution is working...
On Sep 5, 7:28 am, Gene gene.ress...@gmail.com wrote:
I just figured out you are running the first (incorrect) greedy
algorithm I tried. Please try the DP. It works fine.
On Sep 3, 2:18 pm, Discover maniksinghal.n...@gmail.com wrote:
@gene: nice
i think this prob cannot be solved by DP then...
Because anytime a new value coming into the non decreasing sub-array
obtained by the
DP equation can be disrupted(like in the above example).
I think a backtracking approach cud prove useful.
(Recursion)
anytime we get a new element we can do two
1 - 100 of 138 matches
Mail list logo
