You are given a string and a number k. You need to right shift the string k times. What is the efficient way to solve this?

Example:

the string is "Democracy".

If k is 2, then the output should be "cyDemocra".

If k is 3, then the output should be "acyDemocr"

**Answer 1:**

O(nk) time complexity, O(1) space complexity.

where n is the length of the string.

Right shift the string k times.

main() { char s[] = "Some string ...."; int n = streln(s); for(int i=0; i<k; i++) rightShift(s, n); } rightShift(char s[], int length) { char temp = s[length-1]; for(int i=length-1; i>0; i--) s[i]=s[i-1]; s[0] = temp; }

**Answer 2:**

O(n) time complexity, and O(k) space complexity

char s[] = "Some string ...."; int n = streln(s); char *exsp = (char*)calloc(k, sizeof(char)); for(int i=0; i<k; i++) exsp[i]=s[n-k+i]; for(int i=n-1; i>=k; i--) s[i]=s[i-k]; for(int i=0; i<k; i++) s[i]=exsp[i];

**Answer 3:**

O(n) time complexity, O(1) space complexity

Reverse the entire array.

Reverse the array from 0 to k-1, and from k-1 to n-1.

Reverse(char s[], int start, int end) { for(int i=start, j=end; i<j; i++, j--) { int t=s[i]; s[i]=s[j]; s[j]=t; } } Reverse(s, 0, n-1); Reverse(s, 0, k-1); Reverse(s, k, n-1);

Answer 3 is not O(n) time complexity but O(n^2) time complexity

ReplyDeleteHow is it O(n^2) time complexity? The for loop executes at max n iterations only. So, it is O(n) only.

ReplyDelete