constant space vs no additional space and then O(n) time complexity not
possible..
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Mon, May 21, 2012 at 8:01 PM, Dave <dave_and_da...@juno.com> wrote:
> @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/**ms**g/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@**googlegr**oups.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@**googlegr**oups.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@**googlegr**oups.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<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+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 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.
>
--
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.
