1) Take a buffer of 256 chars (char arr[256];) 2) Now traverse the string char by char 3) As you encounter the word increment arr[current_char]++; 4)if the string contains all unique chars then the arr would have either 0 or 1 as elements else >=2
@ankit 1) In place of char array you can take bool array,because we just want to find out whether they repeat or not.we don't need to count them. 2) Please keep in mind consideration for Unicode characters also.
hi a bool array variable has two states false and true... i cant understand how this would help in telling if an element is occurring more than once(i am taking no occurrence as false and occurrence as true).If you want to further reduce the space complexity u can set the bits of an int array.But again a bit can have two states 0,1 so u need to assign 2 bits for a char
@ankit yes you are right since we are interested in finding if a character repeats more than once,so as soon as it is found for first time set its value as 1 and on consecutive occurrence if its value is already one that means it has already occur once so print that character...please check it..
@greatI internally for str.Substring(i + 1, size).Contains(str.Substring(i, 1)) will take o(n^2) because for each characters you are comparing it with rest of characters ahead of it.we could do it in linear time.
Implement a function getbits, that returns the(right adjusted) n bits that begin at position p of an integer. Assume bit position 0 is at the right end and that n and p are sensible positive values.
You are given n real numbers in an array. A number in the array is called a decimal dominant if it occurs more than n/10 times in the array. Give an O(n) time algorithm to determine if the given array has a decimal dominant.
1) Take a buffer of 256 chars (char arr[256];)
ReplyDelete2) Now traverse the string char by char
3) As you encounter the word increment arr[current_char]++;
4)if the string contains all unique chars then the arr would have either 0 or 1 as elements else >=2
@ankit 1) In place of char array you can take bool array,because we just want to find out whether they repeat or not.we don't need to count them.
ReplyDelete2) Please keep in mind consideration for Unicode characters also.
hi
ReplyDeletea bool array variable has two states false and true... i cant understand how this would help in telling if an element is occurring more than once(i am taking no occurrence as false and occurrence as true).If you want to further reduce the space complexity u can set the bits of an int array.But again a bit can have two states 0,1 so u need to assign 2 bits for a char
@ankit yes you are right since we are interested in finding if a character repeats more than once,so as soon as it is found for first time set its value as 1 and on consecutive occurrence if its value is already one that means it has already occur once so print that character...please check it..
ReplyDeleteThis comment has been removed by the author.
ReplyDeletepublic static bool uniqueCheck(string str) {
ReplyDelete// get the size of characters in the str
int size = str.Count;
for (int i=0; i<size-1; i++) {
if (str.Substring(i + 1, size).Contains(str.Substring(i, 1)))
return false;
}
return true;
}
@greatI internally for str.Substring(i + 1, size).Contains(str.Substring(i, 1)) will take o(n^2) because for each characters you are comparing it with rest of characters ahead of it.we could do it in linear time.
ReplyDelete