@arun yes it is,,,,,,
On Tue, Aug 2, 2011 at 2:36 PM, Arun Vishwanathan <aaron.nar...@gmail.com>wrote:
> so can someone please tell me the O(1) space and O(n) time solution to
> this?
> @saurabh :can u explain yr logic?is it an O(1) space solution since u have
> used a 26 element vector?
>
>
>
> On Tue, Jul 19, 2011 at 4:50 AM, saurabh singh <saurab...@gmail.com>wrote:
>
>> 0(n) time o(1) spcae(Dont be too harsh please I am just using 64 bytes of
>> extra space)
>>
>>
>>
>> #include<bitset>
>> #include<iostream>
>> #include<queue>
>> using namespace std;
>> int main()
>> {
>> char answer;
>> bitset<26> charset;
>> bitset<26> repeat;
>> char a[]={'s','a','s','a','b','v','s','a'};
>> #ifdef TEST
>> gets(a);
>> #endif
>> int i;
>> for(i=0;a[i]!='\0';i++){
>> if(charset.test(a[i]-'a')) {
>> repeat.set(a[i]-'a');
>> }
>> charset.set(a[i]-'a');
>> }
>> for(int j=0;j<i;j++)
>> {
>> if(!repeat.test(a[j]-'a')){
>> cout<<a[j]<<endl;
>> return 0;
>> }
>> }
>> cerr<<"No non repeating Character"<<endl;
>> return 0;
>> }
>>
>> On Tue, Jul 19, 2011 at 2:30 AM, Dumanshu <duman...@gmail.com> wrote:
>>
>>> @Sagar: yours is right. but u didn't specify the extra work required
>>> to get the first character non repeating. See the last line of your
>>> solution.
>>>
>>> @Varun: I think we can do this in "single traversal" without bit
>>> vectors x,y but just an array[26], taking chars to be 26.
>>> heres how-
>>> take a variable count =0; arr[26] = {0};
>>> traverse the string
>>> for each character,
>>>
>>> for(i=0;i<str.length;i++)
>>> {
>>> if(arr[str[i]])
>>> arr[str[i]] = -1;
>>> else
>>> arr[str[i]] = (++count);
>>> }
>>> set min = str.length;
>>> index =0;
>>>
>>> for(i=0;i<26;i++)
>>> {
>>> if(arr[i] && arr[i]!=-1)
>>> if(min > arr[i])
>>> {
>>> min = arr[i];
>>> index = i;
>>> }
>>> }
>>>
>>> now print i as %c, its the answer.
>>>
>>>
>>>
>>> On Jul 18, 10:03 pm, sagar pareek <sagarpar...@gmail.com> wrote:
>>> > @dumanshu
>>> > first read my soution just above yours :)
>>> >
>>> >
>>> >
>>> >
>>> >
>>> > On Mon, Jul 18, 2011 at 10:21 PM, Dumanshu <duman...@gmail.com>
>>> wrote:
>>> > > heres my solution with TC O(n) and SC O(26)
>>> > > input string str
>>> > > int arr[26] = {0};
>>> > > traverse the string, character by character and increment the
>>> > > corresponding counter.
>>> > > i.e. arr[str[i]]++;
>>> >
>>> > > Now traverse the string again and print out the first character
>>> > > encountered whose arr[str[i]] == 1;
>>> >
>>> > > On Jul 18, 9:20 pm, sagar pareek <sagarpar...@gmail.com> wrote:
>>> > > > Very good solution :- but space complexity = O(26)
>>> >
>>> > > > take integer array arr[0-25] and initialise it with 0 by taking it
>>> static
>>> > > > logic is that we have only 26 characters so if i want to map
>>> character
>>> > > 'a'
>>> > > > with 0th position of arr[] then it can be done as atoi('a')-97.
>>> > > > so whenever we encounter any character say str[i] (where str is
>>> array of
>>> > > > given string) then it can be incremented as arr[atoi(str[i])-97]++
>>> > > > so traverse the whole str[] and increment the corresponding values
>>> .
>>> > > > At the end those characters which never encounter have values 0 in
>>> arr ,
>>> > > > which encounter only once have values 1 and more than once have
>>> values>1.
>>> > > > at the end traverse the whole arr[] and find out the corresponding
>>> > > character
>>> > > > as itoa(arr[i]+97) :) :)
>>> >
>>> > > > But we have to do extra work to find the first character which
>>> repeats
>>> > > only
>>> > > > once
>>> >
>>> > > > On Mon, Jul 18, 2011 at 8:09 PM, hary rathor <
>>> harry.rat...@gmail.com>
>>> > > wrote:
>>> > > > > can we use bit vector ?
>>> > > > > because by do it we need just 32 bits of one extra variable .
>>> >
>>> > > > > --
>>> > > > > 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.
>>> >
>>> > > > --
>>> > > > **Regards
>>> > > > SAGAR PAREEK
>>> > > > COMPUTER SCIENCE AND ENGINEERING
>>> > > > NIT ALLAHABAD
>>> >
>>> > > --
>>> > > 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.
>>> >
>>> > --
>>> > **Regards
>>> > SAGAR PAREEK
>>> > COMPUTER SCIENCE AND ENGINEERING
>>> > NIT ALLAHABAD- Hide quoted text -
>>> >
>>> > - Show quoted text -
>>>
>>> --
>>> 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.
>>>
>>>
>>
>>
>> --
>> Saurabh Singh
>> B.Tech (Computer Science)
>> MNNIT ALLAHABAD
>>
>>
>> --
>> 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.
>
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT ALLAHABAD
--
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.
