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.
