Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements ofnums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Approach:

The idea is to traverse the array couple of times from left to right once and right to left once keeping track the accumulated product so far from both the sides. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

/** * Return an array of size *returnSize. * Note: The returned array must be malloced, assume caller calls free(). */ vector<int> productExceptSelf(vector<int> &nums) { int numsSize = nums.size(); vector<int> result(numsSize); int temp = 1; // stores the product on the left of each element excluding itself for(int i = 0; i < numsSize; i++){ result[i] = temp; temp = temp * nums[i]; } temp = 1; // stores the product on the left times product on right of each element excluding itself for(int i = numsSize - 1; i >= 0; i--){ result[i] = result[i] * temp; temp = temp * nums[i]; } return result; }

Read More

Reverse String

Write a function that takes a string as input and reverse the same.

Example:

Given s = "hello", return "olleh".

Approach: The idea is to swap the last and the first characters till the middle is reached.

1 2 3 4 5 6 7 8 9 10 11

string reverseString(string &s) { int low = 0, high = s.length() - 1; while(low < high){ char t = s[low]; s[low] = s[high]; s[high] = t; low++; high--; } return s; }

Read More

Reverse Vowels of a String

Write a function that takes a string as input and reverse only the vowels of a string.

Example 1:
Given s = "hello", return "holle".

Approach:  The idea is to traverse the string from both ends while skipping the non-vowels characters from both ends.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

char* reverseVowels(char* s) { int low = 0, high = strlen(s) - 1; char c; while(low < high){ //move forward to skip consonant while(low < strlen(s) && tolower(s[low]) != 'a' && tolower(s[low]) != 'e' && tolower(s[low]) != 'i' && tolower(s[low]) != 'o' && tolower(s[low]) != 'u'){ low++; } //move backward to skip consonant while(low < high && tolower(s[high]) != 'a' && tolower(s[high]) != 'e' && tolower(s[high]) != 'i' && tolower(s[high]) != 'o' && tolower(s[high]) != 'u'){ high--; } if(low < high){ c = s[low]; s[low] = s[high]; s[high] = c; low++; high--; } } return s; }

Read More