@ashish.. it wont be constant space then.. surely it will be o(n) though On Mon, May 21, 2012 at 7:23 PM, Ashish Goel <ashg...@gmail.com> wrote:
> Dave, > > Cant we have a hash table with the item as key and its count as value > (walk over array A and build HT). > For permutation check, walk over second array and start reducing the count > and remove when count becomes zero for that particular key. If some char > not there in HT, return false, else return true. > Best Regards > Ashish Goel > "Think positive and find fuel in failure" > +919985813081 > +919966006652 > > > > On Mon, May 21, 2012 at 6:14 PM, Dave <dave_and_da...@juno.com> wrote: > >> @Piyush: Did you even try this on any examples? If not, try a = {0,1,2,3} >> and b = {0,2,2,2}. >> >> Dave >> >> On Sunday, May 20, 2012 1:39:25 AM UTC-5, Kalyan wrote: >> >>> Piyush. I think we can use your logic. But You should check the product >>> also. >>> Have 4 variables, sum_a,sum_b , prod_a, prod_b >>> >>> Calculate Sum and product of array 'a' and store it in sum_a,prod_a >>> Calculate Sum and product of array 'b' and store it in sum_b,prod_b >>> >>> if sum_a=sum_b && prod_a==prod_b then these 2 arrays are permutations >>> of each other. >>> >>> Space = O(1) >>> Time=O(n) >>> >>> I think this should work. Please correct me if you find mistakes. >>> >>> On 5/20/12, anuj agarwal <coolbuddy...@gmail.com> wrote: >>> > U are checking if the sum is same or not.. which can be same even if >>> the >>> > elements are different. >>> > >>> > On Sun, May 20, 2012 at 11:54 AM, Piyush Khandelwal < >>> > piyushkhandelwal...@gmail.com> wrote: >>> > >>> >> Hiii!! I have some idea about the solution. Please notify me if i am >>> >> wrong.... >>> >> >>> >> a= [ 4,3,5 ] and b= [ 3,5,4 ] >>> >> diff=0; >>> >> for (i=0; i<n;i++) >>> >> { diff= diff+a[i]-b[i]; >>> >> } >>> >> if diff == 0 >>> >> print: permutation >>> >> else >>> >> print: not permutation >>> >> >>> >> >>> >> >>> >> >>> >> >>> >> On 20 May 2012 07:2 0, Dave <dave_and_da...@juno.com> wrote: >>> >> >>> >>> @Harshit: These are a few unanswered questions that came to mind >>> when I >>> >>> read your solution attempt: What do you do with negative elements? >>> What >>> >>> is >>> >>> the -12th prime number? How do you deal with overflow in the cases >>> where >>> >>> you have a lot of large prime numbers and the product exceeds your >>> native >>> >>> data types? >>> >>> >>> >>> Dave >>> >>> >>> >>> On Saturday, May 19, 2012 2:29:52 PM UTC-5, harshit pahuja wrote: >>> >>> >>> >>>> given 2 unsorted integer arrays a and b of equal size. Determine if >>> b is >>> >>>> a permutation of a. Can this be done in O(n) time and O(1) space ? >>> >>>> >>> >>>> >>> >>>> >>> >>>> >>> >>>> please help me with my solution >>> >>>> >>> >>>> >>> >>>> suppose a -- 3 5 4 >>> >>>> b -- 4 3 5 >>> >>>> >>> >>>> now we replace a[i] with a[i]..th prime number and b with b[i] .. >>> th >>> >>>> prime number >>> >>>> >>> >>>> now array a becomes 5 11 7 >>> >>>> array b becomes 7 5 11 >>> >>>> >>> >>>> now we take product of elements of array a and do the same with >>> array b >>> >>>> elements >>> >>>> if product is equal then b is a permutation of a >>> >>>> >>> >>> -- >>> >>> 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/-/WEW0M5VUUVEJ<https://groups.google.com/d/msg/algogeeks/-/WEW0M5VUUVEJ>. >>> >>> >>> >>> >>> To post to this group, send email to algogeeks@googlegroups.com. >>> >>> To unsubscribe from this group, send email to >>> >>> algogeeks+unsubscribe@**googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>. >>> >>> >>> For more options, visit this group at >>> >>> http://groups.google.com/**group/algogeeks?hl=en<http://groups.google.com/group/algogeeks?hl=en>. >>> >>> >>> >>> >> >>> >> >>> >> >>> >> -- >>> >> *Piyush Khandelwal*** >>> >> Mobile No: 91-8447229204 >>> >> 91-9808479765 >>> >> >>> >> >>> >> -- >>> >> 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+unsubscribe@**googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>. >>> >>> >> For more options, visit this group at >>> >> http://groups.google.com/**group/algogeeks?hl=en<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 algogeeks@googlegroups.com. >>> > To unsubscribe from this group, send email to >>> > algogeeks+unsubscribe@**googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>. >>> >>> > For more options, visit this group at >>> > http://groups.google.com/**group/algogeeks?hl=en<http://groups.google.com/group/algogeeks?hl=en>. >>> >>> > >>> > >>> >>> >>> -- >>> * >>> * >>> >>> *Kalyanasundaram N* >>> >>> *BE 2nd year, CSE* >>> >>> *College of Engineering Guindy,* >>> >>> *Chennai-600025* >>> * >>> * >>> >> -- >> 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/-/i-WLn7rdzDYJ. >> >> 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, 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 algogeeks@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 algogeeks@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.