[algogeeks] Re: find duplicate and missing element
what do u think about this ...its O(n) program.. #include #include # include "malloc.h" # include bool bRemoveDuplicates(int array[], int iSize){ if(iSize <1) return false; if(array == NULL) return false; if(iSize == 1) return true; int left_comp = 0; int right_comp = 1; bool start_move = false; int flag=0; int hole =0; //{1,1,1,1,1,1,1,1,2,2,4,5,7,8,8,9,9,10,11,11,12,13,14}; for(; right_comp >i; } -- 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
if input is 12345 then the output should be 54321 -- 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.
[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 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.
[algogeeks] Re: Amazon interview Question (Array yet again!)
nice explanation gene :) On Sep 2, 8:35 am, Gene 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 > > #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 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: 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 wrote: > @Gene: Thanks alot! :-) your solution works like charm! > > On Aug 28, 7:09 am, Gene 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 > > > 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 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] 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: Take 5 digit number and find 2 power that number.............
But how the number(in decimal form) will be displayedif ques demands so. On Sep 2, 1:49 pm, saurabh singh wrote: > Suppose the number of shifts be x. > Also let the integer be represented by 16 bits on that machine. > Now take int n= (int)(x/16 + 0.5), to take the upper cap on result :) . > SO having 2^x will be same as doing 2<<(x-1) so essentially if we represent > the resultant number in a linked list of nodes, where each node can store an > integer, then the bit position at 2+x-1=x+1 will be set as 1 and this > (x+1)th nit will fall in (x+1)/16th node in linked list also in that node > (x+1)%16 will give the position of bit to be set. > > On Thu, Sep 2, 2010 at 1:32 PM, ashish agarwal > > > > > > wrote: > > I think it will be 1< > > On Wed, Sep 1, 2010 at 10:53 PM, Yan Wang wrote: > > >> Maybe you misunderstand the question. > >> The question is how to compute 2^X where 0 <= X <= 9? > >> How? > > >> On Wed, Sep 1, 2010 at 10:48 PM, Ruturaj wrote: > >> > a 5 digit number is of order 10^5 which is << 10^16 of which int in C > >> > is of size. > >> > Just multiply both numbers. > > >> > On Sep 2, 10:39 am, prasad rao wrote: > >> >> Program that takes a 5 digit number and calculates 2 power that number > >> and > >> >> prints it and should not use the Big-integer and Exponential > >> Function's. > > >> > -- > >> > 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 >> .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 >> .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 > .com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > Thanks & Regards, > Saurabh -- 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: Amazon intern Question
Trie-traverse search will be best.. On Thu, Sep 2, 2010 at 8:10 PM, Manjunath Manohar wrote: > 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.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.
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 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 > 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 > 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 > >> 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 > >> > 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 > 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 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
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 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 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 >> 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 >> > wrote: >> >> >> >> >> >> On Wed, Sep 1, 2010 at 11:08 AM, Dhritiman Das >> >> 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 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 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...@goo