ya that's right :( any other solution..
On Saturday, 14 July 2012 03:24:41 UTC+5:30, Dave wrote:
>
> @Jatin: Take the array {1, 2, 4, 8, ..., x, 2, 4, 8, ..., x, x}, where x
> is the largest power of two that will fit in your integer data type. Here 1
> occurs once, 2, 4, 8, ... each occur twice, and x occurs three times.
> Ignoring that you can't calculate the product of the numbers due to
> overflow, the cube of each number in the array will be a factor of the
> product, so you will have to check every number to see if it occurs three
> times. Those checks will be O(n), so the whole algorithm will be O(n^2).
> Correct me if I am wrong.
>
> As another example, just include a zero in the array and see if your
> algorithm still works as written.
>
> Dave
>
> On Friday, July 13, 2012 9:59:31 AM UTC-5, jatin sethi wrote:
>
>> as long as we are using goto with proper comments to ensure that it
>> won't decrease the readability we can use them and ther's no harm in it!
>> Secondly the worst case for my algo is o(n) .?..correct me if i am wrong
>> On Friday, 13 July 2012 18:12:41 UTC+5:30, adarsh kumar wrote:
>>
>>> Ya I didn't see that part, sorry. And in general, using goto is not
>>> advisable.
>>> Plus this will exceed O(n) in the worst case, as we may keep visiting
>>> the goto again and again. Not sure of its exact time complexity.
>>> ------------------------------
>>> From: vindhya chhabra
>>> Sent: 13-07-2012 17:46
>>> To: [email protected]
>>> Subject: Re: [algogeeks] Re: Amazon Interview Question
>>>
>>> @adarsh
>>> But i think jatin has asked to check for the number( we achieved in step
>>> 1) occuring thrice or not..and in this check 27 will rule out.but i doubt
>>> the algo given by Jatin runs in O(n) time. please comment.
>>>
>>> On Fri, Jul 13, 2012 at 5:17 PM, adarsh kumar <[email protected]>wrote:
>>>
>>>> @jatin:
>>>> Your first method may be proved wrong.
>>>>
>>>> Here is a counter test case:
>>>>
>>>> Suppose the array is:
>>>>
>>>> 27 729 19683 2 3 3 27 3 81 729
>>>>
>>>> Here, 81 occurs once, 19683 occurs once, 2 occurs once,729 occurs
>>>> twice, 27 occurs twice, and 3 occurs thrice.
>>>>
>>>> You are supposed to return 3
>>>> But as per your method, the product will be computed as
>>>> 729*19683*2*3*3*27*3*81*729=product(say)
>>>>
>>>> Upon traversing the second time, it will return 27, as
>>>> product%(27*27*27) is equal to zero!
>>>>
>>>> regards.
>>>>
>>>>
>>>>
>>>> On Fri, Jul 13, 2012 at 1:29 PM, @jatin <[email protected]> wrote:
>>>>
>>>>> Or we can make a BST from array list in ----o(n)
>>>>> then traverse it inorder-----o(logn)
>>>>>
>>>>> but this solution requires o(logn) space though.
>>>>>
>>>>> On Friday, 13 July 2012 13:16:50 UTC+5:30, jatin sethi wrote:
>>>>>
>>>>>>
>>>>>> 1)Find product of the array and store it in say prod ---- o(n) and
>>>>>> o(1)
>>>>>> 2)now traverse the array and check if
>>>>>>
>>>>>> static int i;
>>>>>> tag:
>>>>>> while(i<n)
>>>>>> if( prod %(ar[i]*arr[i]*arr[i] ) ==0)
>>>>>> break;
>>>>>> //this may be the required element
>>>>>> //e-o-while
>>>>>>
>>>>>> //now check is this is the element that is occuring three times
>>>>>> ----o(n)
>>>>>> if(number is not the required one then)
>>>>>> goto tag;
>>>>>>
>>>>>> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
>>>>>>
>>>>>>> Given an array of integers where some numbers repeat once, some
>>>>>>> numbers repeat twice and only one number repeats thrice, how do you
>>>>>>> find
>>>>>>> the number that gets repeated 3 times?
>>>>>>>
>>>>>>> Does this problem have an O(n) time and O(1) space solution?
>>>>>>> No hashmaps please!
>>>>>>>
>>>>>> --
>>>>> 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/-/lmzhJ-GSdigJ.
>>>>>
>>>>> To post to this group, send email to [email protected].
>>>>> To unsubscribe from this group, send email to
>>>>> [email protected].
>>>>> 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 [email protected].
>>>> To unsubscribe from this group, send email to
>>>> [email protected].
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>
>>>
>>>
>>>
>>> --
>>> Vindhya Chhabra
>>>
>>>
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected].
>>> 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/-/r8KWdIC96ckJ.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
