@Ashish: Using a hash table violates the O(1) space requirement given in
the original problem.
Dave
On Monday, May 21, 2012 8:53:44 AM UTC-5, ashgoel 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 view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/Hcg4PMiUBioJ.
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.
