Re: [algogeeks] Re: find duplicate and missing element
Yeah
The solution given by Ankit is gr8. But inorder to not destroy the array we
need to go by the geek method where
Suppose x is the duplicated element and y is the missing element in the
array.
Multiply all the elements in the array to prod and sum all the elements in
the array to sum.
Divide prod with 100! that is gonna give value of x/y
Subtract sum from 5050 that is gonna give 5050 + x - y
Solve the two equations to get x and y.
It is gonna take O(N) ideally.
Cheers
Kartheek
On Fri, Sep 3, 2010 at 11:09 AM, Ankit Sinha akki12...@gmail.com wrote:
@Dhritiman, It's good algo man!!!The only thing is we are destroying
the array but also that's mandatory as only o(n) complexity we are
interested in.
As Somebody wanted the code, here I am attaching below: -
int a[SIZE_A] = {0,2,1,4,0};
int i = 0, dup = 0, pos = 0, t =0;
while (i 5)
{
if (a[i] == i)
i++;
else if (a[a[i]] == a[i])
{
dup = a[i];
printf (\nduplicated element is [%d], dup);
pos = i;
i++;
}
else
{
t= a[i];
a[i] = a[a[i]];
a[t] = t;
}
}
printf (\nmissing element is [%d], pos);
Cheers,
Ankit Sinha
On Thu, Sep 2, 2010 at 7:08 AM, Dhritiman Das dedhriti...@gmail.com
wrote:
@Dinesh,
Yes, we can't apply this method, if that's not allowed.
On Thu, Sep 2, 2010 at 10:31 AM, dinesh bansal bansal...@gmail.com
wrote:
On Wed, Sep 1, 2010 at 11:08 AM, Dhritiman Das dedhriti...@gmail.com
wrote:
Given a array, A[1..n], do the following.
Start from i=1 and try placing each number in its correct position in
the
array.
If the number is already in its correct position, go ahead. if (A[i] ==
i) , i++
else if the number was already restored to its correct position, then
it
is
a duplicate , so remember it and move ahead if (A[A[i]] == A[i]), dup =
A[i], i++ ;
else
swap the elements at the current index i and that at A[i]'s correct
position in the array.
continue this until all numbers are placed in their correct position in
the array
Finally, A[missing] will be dup.
O(n)
@Dharitiman, good solution man. No expensive computation, no extra
memory
required. Only problem is it will change the input array to sorted order
which may not be desired.
On Wed, Sep 1, 2010 at 7:14 AM, Dave dave_and_da...@juno.com wrote:
Suppose that x is duplicated and y is omitted. Then the sum of the
numbers would be 5050 + x - y. Similarly, the sums of the squares of
the numbers would be 338,350 + x^2 - y^2. Calculate the sum and sum of
squares of the numbers and solve the resulting equations for x and y.
Dave
On Aug 31, 1:57 pm, Raj Jagvanshi raj.jagvan...@gmail.com wrote:
There is an array having distinct 100 elements from 1 to 100
but by mistake some no is duplicated and a no is missed.
Find the duplicate no and missing no.
Thanks
Raj Jagvanshi
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Dinesh Bansal
The Law of Win says, Let's not do it your way or my way; let's do it
the
best way.
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Re: [algogeeks] Re: find duplicate and missing element
@kartheek, thanks for ur input!! Certainly, ur soln is fine but only
will cater when array is 1...n but what if it ranges for 0...n-1. The
algo given by dhritiman fits in all the scenario. but ofcourse for
given question ( 1 to 100) your mathematical approach is good. :)...
Cheers,
Ankit Sinha!!!
On Fri, Sep 3, 2010 at 8:14 AM, kartheek muthyala
kartheek0...@gmail.com wrote:y
Yeah
The solution given by Ankit is gr8. But inorder to not destroy the array we
need to go by the geek method where
Suppose x is the duplicated element and y is the missing element in the
array.
Multiply all the elements in the array to prod and sum all the elements in
the array to sum.
Divide prod with 100! that is gonna give value of x/y
Subtract sum from 5050 that is gonna give 5050 + x - y
Solve the two equations to get x and y.
It is gonna take O(N) ideally.
Cheers
Kartheek
On Fri, Sep 3, 2010 at 11:09 AM, Ankit Sinha akki12...@gmail.com wrote:
@Dhritiman, It's good algo man!!!The only thing is we are destroying
the array but also that's mandatory as only o(n) complexity we are
interested in.
As Somebody wanted the code, here I am attaching below: -
int a[SIZE_A] = {0,2,1,4,0};
int i = 0, dup = 0, pos = 0, t =0;
while (i 5)
{
if (a[i] == i)
i++;
else if (a[a[i]] == a[i])
{
dup = a[i];
printf (\nduplicated element is [%d], dup);
pos = i;
i++;
}
else
{
t= a[i];
a[i] = a[a[i]];
a[t] = t;
}
}
printf (\nmissing element is [%d], pos);
Cheers,
Ankit Sinha
On Thu, Sep 2, 2010 at 7:08 AM, Dhritiman Das dedhriti...@gmail.com
wrote:
@Dinesh,
Yes, we can't apply this method, if that's not allowed.
On Thu, Sep 2, 2010 at 10:31 AM, dinesh bansal bansal...@gmail.com
wrote:
On Wed, Sep 1, 2010 at 11:08 AM, Dhritiman Das dedhriti...@gmail.com
wrote:
Given a array, A[1..n], do the following.
Start from i=1 and try placing each number in its correct position in
the
array.
If the number is already in its correct position, go ahead. if (A[i]
==
i) , i++
else if the number was already restored to its correct position, then
it
is
a duplicate , so remember it and move ahead if (A[A[i]] == A[i]), dup
=
A[i], i++ ;
else
swap the elements at the current index i and that at A[i]'s correct
position in the array.
continue this until all numbers are placed in their correct position
in
the array
Finally, A[missing] will be dup.
O(n)
@Dharitiman, good solution man. No expensive computation, no extra
memory
required. Only problem is it will change the input array to sorted
order
which may not be desired.
On Wed, Sep 1, 2010 at 7:14 AM, Dave dave_and_da...@juno.com wrote:
Suppose that x is duplicated and y is omitted. Then the sum of the
numbers would be 5050 + x - y. Similarly, the sums of the squares of
the numbers would be 338,350 + x^2 - y^2. Calculate the sum and sum
of
squares of the numbers and solve the resulting equations for x and y.
Dave
On Aug 31, 1:57 pm, Raj Jagvanshi raj.jagvan...@gmail.com wrote:
There is an array having distinct 100 elements from 1 to 100
but by mistake some no is duplicated and a no is missed.
Find the duplicate no and missing no.
Thanks
Raj Jagvanshi
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Dinesh Bansal
The Law of Win says, Let's not do it your way or my way; let's do it
the
best way.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this
Re: [algogeeks] Re: find duplicate and missing element
@ankit
Yup I got your point. I didn't see the algo given by dhritiman previously. I
think that is better than my solution , where it fits in all cases.
Cheers
Kartheek
On Fri, Sep 3, 2010 at 1:32 PM, Ankit Sinha akki12...@gmail.com wrote:
@kartheek, thanks for ur input!! Certainly, ur soln is fine but only
will cater when array is 1...n but what if it ranges for 0...n-1. The
algo given by dhritiman fits in all the scenario. but ofcourse for
given question ( 1 to 100) your mathematical approach is good. :)...
Cheers,
Ankit Sinha!!!
On Fri, Sep 3, 2010 at 8:14 AM, kartheek muthyala
kartheek0...@gmail.com wrote:y
Yeah
The solution given by Ankit is gr8. But inorder to not destroy the array
we
need to go by the geek method where
Suppose x is the duplicated element and y is the missing element in the
array.
Multiply all the elements in the array to prod and sum all the elements
in
the array to sum.
Divide prod with 100! that is gonna give value of x/y
Subtract sum from 5050 that is gonna give 5050 + x - y
Solve the two equations to get x and y.
It is gonna take O(N) ideally.
Cheers
Kartheek
On Fri, Sep 3, 2010 at 11:09 AM, Ankit Sinha akki12...@gmail.com
wrote:
@Dhritiman, It's good algo man!!!The only thing is we are destroying
the array but also that's mandatory as only o(n) complexity we are
interested in.
As Somebody wanted the code, here I am attaching below: -
int a[SIZE_A] = {0,2,1,4,0};
int i = 0, dup = 0, pos = 0, t =0;
while (i 5)
{
if (a[i] == i)
i++;
else if (a[a[i]] == a[i])
{
dup = a[i];
printf (\nduplicated element is [%d], dup);
pos = i;
i++;
}
else
{
t= a[i];
a[i] = a[a[i]];
a[t] = t;
}
}
printf (\nmissing element is [%d], pos);
Cheers,
Ankit Sinha
On Thu, Sep 2, 2010 at 7:08 AM, Dhritiman Das dedhriti...@gmail.com
wrote:
@Dinesh,
Yes, we can't apply this method, if that's not allowed.
On Thu, Sep 2, 2010 at 10:31 AM, dinesh bansal bansal...@gmail.com
wrote:
On Wed, Sep 1, 2010 at 11:08 AM, Dhritiman Das
dedhriti...@gmail.com
wrote:
Given a array, A[1..n], do the following.
Start from i=1 and try placing each number in its correct position
in
the
array.
If the number is already in its correct position, go ahead. if (A[i]
==
i) , i++
else if the number was already restored to its correct position,
then
it
is
a duplicate , so remember it and move ahead if (A[A[i]] == A[i]),
dup
=
A[i], i++ ;
else
swap the elements at the current index i and that at A[i]'s
correct
position in the array.
continue this until all numbers are placed in their correct position
in
the array
Finally, A[missing] will be dup.
O(n)
@Dharitiman, good solution man. No expensive computation, no extra
memory
required. Only problem is it will change the input array to sorted
order
which may not be desired.
On Wed, Sep 1, 2010 at 7:14 AM, Dave dave_and_da...@juno.com
wrote:
Suppose that x is duplicated and y is omitted. Then the sum of the
numbers would be 5050 + x - y. Similarly, the sums of the squares
of
the numbers would be 338,350 + x^2 - y^2. Calculate the sum and sum
of
squares of the numbers and solve the resulting equations for x and
y.
Dave
On Aug 31, 1:57 pm, Raj Jagvanshi raj.jagvan...@gmail.com wrote:
There is an array having distinct 100 elements from 1 to 100
but by mistake some no is duplicated and a no is missed.
Find the duplicate no and missing no.
Thanks
Raj Jagvanshi
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Dinesh Bansal
The Law of Win says, Let's not do it your way or my way; let's do it
the
best way.
--
You received this message because you are subscribed to the Google
Re: [algogeeks] Re: Amazon intern Question
Trie-traverse search will be best.. On Thu, Sep 2, 2010 at 8:10 PM, Manjunath Manohar manjunath.n...@gmail.comwrote: trie will be the best choice for this.. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Dhruvesh Kumar Mobile No.: +919911314113 M.C.A., Department of Computer Science, Delhi University, INDIA -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Simple reVerse
int reverse(int x)
{
...
...
}
complete the above code such that it returns the reverse of 'x'
condition here is u should not use loops and global as well as static
variable..
try to give all the possible solutions for this ...
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon interview Question (Array yet again!)
@gene: nice solution..
but it's not working for a[]={20,22,13,11};
ur code will give soln : 24
but ans should be: 22 {11,11,11,11}
pls correct me if i m wrong
On Aug 28, 8:26 am, jagadish jagadish1...@gmail.com wrote:
@Gene: Thanks alot! :-) your solution works like charm!
On Aug 28, 7:09 am, Gene gene.ress...@gmail.com wrote:
This is a nice problem. It looks like a trivial matroid, so a greedy
algorithm will work fine. The obvious greedy algorithm is to work
left-to-right and incorporate elements into the sorted order one-by-
one. In each case, you have 2 choices. The first is to decrement
elements to the left by the amount needed to restore non-decreasing
order. The second is to delete the new element. The cost of each is
easy to calculate. Pick the choice with least cost and continue.
This algorithm is O(n^2). There may be a faster way to do it, but I
can't see one.
#include stdio.h
int make_nondecreasing(int *a, int n)
{
int i, j, dec, dec_cost, total_cost;
total_cost = 0;
for (i = 0; i n - 1; i++) {
// If we find a decrease...
if (a[i] a[i + 1]) {
// Find cost of decrementing all to the left.
dec_cost = dec = a[i] - a[i + 1];
for (j = i - 1; j = 0; j--) {
// Find decrement that would be needed.
dec += a[j] - a[j + 1];
// If no decement, we're done.
if (dec = 0)
break;
// Count cost of decrement.
dec_cost += dec;
}
// Compare decrement cost with deletion cost.
if (dec_cost a[i + 1]) {
// Decrement is cheaper. Do it.
for (j = i; j = 0; j--) {
if (a[j] a[i + 1])
a[j] = a[i + 1];
}
total_cost += dec_cost;
}
else {
// Deletion is cheaper. Do it.
total_cost += a[i + 1];
for (j = i + 1; j n - 1; j++)
a[j] = a[j + 1];
--n;
}
}
}
return total_cost;
}
int main(void)
{
int a[] = { 14, 15, 16, 13, 11, 18 };
//int a[] = { 4, 3, 5, 6};
//int a[] = { 10, 3, 11, 12 };
int cost = make_nondecreasing(a, sizeof a / sizeof a[0]);
printf(cost=%d\n, cost);
return 0;
}
On Aug 27, 12:15 pm, jagadish jagadish1...@gmail.com wrote:
You are given an array of positive integers. Convert it to a sorted
array with minimum cost. Only valid operation are
1) Decrement - cost = 1
2) Delete an element completely from the array - cost = value of
element
For example:
4,3,5,6, - cost 1
10,3,11,12 - cost 3
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon interview Question (Array yet again!)
nice explanation gene :)
On Sep 2, 8:35 am, Gene gene.ress...@gmail.com wrote:
Okay. First, you can make the DP more efficient than the one I gave
earlier. You don't need to scan the whole previous column when
calculating costs of decrementing. Rather there are only two
possibilities.
I will add that rahul patil's solution looks correct, but it's
exponential time. DP is better for this problem.
Remember C(n, m) is the cost of making a[1 .. n] into a non-decreasing
sequence with the last element being no more than m. And we always
draw m from the set V of values in a.
So here is the new DP:
C(1, m) = max(a[1] - m, 0) // first row only decrement is possible
C(n, m) = min (
a[n] + C(n - 1, m), // delete
(a[n] = m) ? C(n - 1, a[n]) : C(n - 1, m) + a[n] - m // decrement
)
In case you don't follow, the //delete line is saying that we
already know the cost of making everything up to element n-1 non-
decreasing and no more than m. This, by recursive assumption, is just
C(n-1,m). The additional cost of deleting a[n] is a[n].
The //decrement line is similar, but there are 2 cases. If a[n] is
more than m, we must decrement it. The cost here consists of making
everything up to n-1 non-decreasing and no more than m, i.e. C(n-1,m).
Plus we have the cost of chopping a[n] down to m, which is a[n]-m.
In the other case, a[n] is m or less. So there's no need to
decrement, but we must get the elements a[1..n-1] to be no more than
a[n]. Again by recursive assumption this cost is C(n-1,a[n]).
Here is an example. Suppose we have a = [5, 1, 1, 1, 3, 1]. The
least cost here is obtained by decrementing the 5 to 1 (cost 4) and
deleting the final 1 (cost 1) for a total cost of 5.
So let's try the algorithm. (You must view this with a fixed font.)
Table of C(n, m) values:
m = 1 3 5
n = 1 : 4 2 0
n = 2 : 4 3* 1*
n = 3 : 4 4 2*
n = 4 : 4 4 3*
n = 5 : 6m 4 4
n = 6 : 6 5* 5*
Here * means C resulted from decrementing and m means that a
decrement was based on the value of m rather than a[n].
We take the answer from C(6,5) = 5.
Implementing this is a little tricky because m values are drawn from
V. You could use a hash table for the m-axis. But it's more
efficient to store V in an array and convert all the values of m in
the DP into indices of V. Because all the indices lie in [ 1 .. |
V| ], we can use simple arrays rather than hash tables to represent
the rows of the table C.
We only need 2 rows at a time, so O(|V|) storage does the job.
For C, we also need to convert all the indices to origin 0.
So here's the final O(n^2) code. I think this is a correct
implementation. If anyone has an example that breaks it, I'd like to
see.
#include stdio.h
#define NMAX 1
int cost(int *a, int N)
{
int i, j, max, Nv;
int V[NMAX], A[NMAX], B[NMAX];
int *Cm = A, *Cn = B; // (n-1)'th and n'th rows of C
// Compute set V with no duplicates.
// Remember where max element is.
Nv = max = 0;
for (i = 0; i N; i++) {
for (j = 0; j Nv; j++)
if (a[i] == V[j])
break;
if (j == Nv) {
V[Nv++] = a[i];
if (V[j] V[max])
max = j;
}
a[i] = j; // Convert a to indices.
}
// Fill in first row of C.
for (i = 0; i Nv; i++)
Cm[i] = (V[a[0]] = V[i]) ? V[a[0]] - V[i] : 0;
// Fill in the rest of the rows of C.
for (i = 1; i N; i++) {
for (j = 0; j Nv; j++) {
int del = Cm[j] + V[a[i]];
int dec = (V[a[i]] = V[j]) ? Cm[a[i]] : Cm[j] + V[a[i]] - V[j];
Cn[j] = (del dec) ? del : dec;
}
// Swap row buffers so current becomes previous.
int *tmp = Cn; Cn = Cm; Cm = tmp;
}
return Cm[max];
}
int main(void)
{
static int a[] = { 5, 1, 1, 1, 3, 1 };
printf(Min cost = %d\n, cost(a, sizeof a / sizeof a[0]));
return 0;
}
On Aug 30, 9:19 pm, vikash jain vikash.ro...@gmail.com wrote:
@gene ..if u just give an example herethat will make things more
clear...
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Simple reVerse
I presume that you mean reversing the order of the bits, so that the
low-order bit goes to the high-order position and vice-versa. Assuming
32 bit integers, this does the trick:
int r;
r = ( ( x 0x ) 16 ) || ( ( x 0x )
16 );
r = ( ( r 0xff00ff00 ) 8 ) || ( ( r 0x00ff00ff )
8 );
r = ( ( r 0xf0f0f0f0 ) 4 ) || ( ( r 0x0f0f0f0f )
4 );
r = ( ( r 0x ) 2 ) || ( ( r 0x )
2 );
r = ( ( r 0x ) 1 ) || ( ( r 0x )
1 );
return r;
Dave
On Sep 3, 1:00 pm, Albert alberttheb...@gmail.com wrote:
int reverse(int x)
{
...
...
}
complete the above code such that it returns the reverse of 'x'
condition here is u should not use loops and global as well as static
variable..
try to give all the possible solutions for this ...
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Simple reVerse
@Dave but i tried the code its not working Its giving 1 for all the input could u explain the code please -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
