Use bitwise hashmap.
On Thu, Jan 30, 2014 at 8:46 PM, Don <dondod...@gmail.com> wrote:
> No. If you start at any number in a sequence it will find the entire
> sequence. There is no need to start again at some other number in that
> sequence.
>
> Don
>
>
> On Wednesday, January 29, 2014 12:19:21 AM UTC-5, Varun Sachdeva wrote:
>
>> If we don't process the same number more than once, does it not create a
>> situation when we miss out on the solution?
>> For example the digit 6 in this sequence:
>> 1,2,3,4,0,2,3,1,4,5,2,4,3,4,5,6,7,8,9
>>
>> Varun
>>
>>
>> Varun Sachdeva
>>
>>
>>
>> On 28 January 2014 00:29, Don <dond...@gmail.com> wrote:
>>
>>> This works, and I think is O(N*log(N)) which is similar to sorting and
>>> scanning.
>>>
>>> An unordered map will be faster, in general. It could be made faster in
>>> most cases by looping over items left in the map, to avoid processing the
>>> same number more than once. Also, when the number of items left in the map
>>> is less than max, there is no need to continue because you know they can't
>>> form a sequence longer than max.
>>>
>>> int longest_sequence(vector<int> &nums)
>>> {
>>> unordered_map<int,bool> mp;
>>> int max = 0;
>>> for(unsigned int i = 0; i < nums.size(); i++)
>>> mp[nums[i]] = true;
>>>
>>> while(mp.size() > max)
>>> {
>>> int i;
>>> int n = mp.begin()->first; // Pick first item in map
>>> mp.erase(n);
>>> int count = 1;
>>> for(i = n+1; mp.contains(i); ++i)
>>> {
>>> ++count;
>>> mp.erase(i);
>>> }
>>> for(i = n-1; mp.contains(i); --i)
>>> {
>>> ++count;
>>> mp.erase(i);
>>> }
>>>
>>> if (count > max) max = count;
>>> }
>>>
>>> return max;
>>> }
>>>
>>>
>>>
>>> On Monday, January 27, 2014 9:17:56 AM UTC-5, Nishant Pandey wrote:
>>>
>>>> I think this the most optimized code i have writen :
>>>>
>>>> #include <iostream>
>>>> #include <vector>
>>>> #include <map>
>>>> using namespace std;
>>>>
>>>> int longest_sequence(vector<int> &nums) {
>>>> map<int,bool> mp;
>>>> int count;
>>>> int max = -9999;
>>>> int n = 0;
>>>> for(unsigned int i = 0; i < nums.size(); i++) {
>>>> mp[nums[i]] = true;
>>>> }
>>>>
>>>> for(unsigned int i =0;i<nums.size();i++) {
>>>> n = nums[i];
>>>> mp.erase(n);
>>>> count = 1;
>>>> while(mp.find(n+1)!= mp.end()) {
>>>> count++;
>>>> mp.erase(n+1);
>>>> n++;
>>>> }
>>>> n = nums[i];
>>>> while(mp.find(n-1)!= mp.end()) {
>>>> count++;
>>>> mp.erase(n-1);
>>>> n--;
>>>> }
>>>> if(count > max) {
>>>> max = count;
>>>> }
>>>> }
>>>> return max;
>>>> }
>>>>
>>>> int main() {
>>>> // your code goes here
>>>> cout << "Jai Ganesha";
>>>> vector<int> vc;
>>>> vc.push_back(5);
>>>> vc.push_back(20);
>>>> vc.push_back(45);
>>>> vc.push_back(3);
>>>> vc.push_back(98);
>>>> vc.push_back(4);
>>>> vc.push_back(21);
>>>> vc.push_back(1);
>>>> vc.push_back(99);
>>>> vc.push_back(2);
>>>> cout << endl << longest_sequence(vc);
>>>> return 0;
>>>> }
>>>>
>>>>
>>>>
>>>> NIshant Pandey
>>>> Cell : 9911258345
>>>> Voice Mail : +91 124 451 2130
>>>>
>>>>
>>>>
>>>>
>>>> On Mon, Jan 27, 2014 at 4:29 PM, Amol Sharma <amolsh...@gmail.com>wrote:
>>>>
>>>>> Given an array of positive numbers arranged in any order. You have
>>>>> to find the length of longest continuos(difference of +1, -1) sequence in
>>>>> the array.
>>>>>
>>>>> for eg.
>>>>> A[] = *5*, 20, 45, *3*, 98, *4*, 21, *1*, 99, *2*
>>>>>
>>>>> then longest continuos subsequence is [1, 2, 3, 4, 5] and hence the
>>>>> output should be *"5"*, the length of this sequence.
>>>>>
>>>>> Other Continuos sequence are -
>>>>>
>>>>> [20, 21]
>>>>> [45]
>>>>> [98, 99]
>>>>> [21]
>>>>>
>>>>> A[i] can be > 10^6, so hashing is not an option.
>>>>>
>>>>> Possible Approach is by sorting and time complexity will be O(nlogn).
>>>>>
>>>>> Does anyone have better approach for this ?
>>>>>
>>>>>
>>>>>
>>>>> --
>>>>> Thanks and Regards,
>>>>> Amol Sharma
>>>>>
>>>>> --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "Algorithm Geeks" group.
>>>>> To unsubscribe from this group and stop receiving emails from it, send
>>>>> an email to algogeeks+...@googlegroups.com.
>>>>>
>>>>
>>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an email to algogeeks+...@googlegroups.com.
>>>
>>
>> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
