Convert a string having Roman numerals to an integer

© Parineeth M R

Question 27. Convert a string having Roman numerals into an integer


The integer equivalent for the roman numerals is given below

To find the integer equivalent of a string containing roman numerals, we process the string from the rear. This simplifies the computation. If the current roman numeral is greater than the next numeral, we add the current numeral to the result. For instance consider XI. When processing X, since X is greater than I, we add 10 to the result. If the current roman numeral is less than the next numeral, then we subtract the current numeral from the result. For instance consider IX. When processing I, since I is less than X, we subtract 1 from the result.

C/C++


/*Helper function that returns the numeric value of a Roman alphabet*/
int get_numeric_value(char c)
{
	int result;

	switch(c) {
		case 'I': result = 1; break;
		case 'V': result = 5; break;
		case 'X': result = 10; break;
		case 'L': result = 50; break;
		case 'C': result = 100; break;
		case 'D': result = 500; break;
		case 'M': result = 1000; break;
		default: result = 0; break;
	}
	return result;
}


/* 
Main function that converts a Roman string into an integer
str1: valid input string with Roman alphabets
Return value: integer equivalent of the Roman string
*/
int roman_to_int(char *str1) 
{
	int i, result;
	
	/*Process the string from the rear*/
	i = strlen(str1) - 1;
	if (i < 0)
		return 0;
	
	result = get_numeric_value(str1[i]);
	--i;
	while (i >= 0) {
		int cur_value = get_numeric_value(str1[i]);
		int next_value = get_numeric_value(str1[i+1]);

		if (cur_value < next_value)
			result -= cur_value;
		else
			result += cur_value;		
			
		--i;
	}
	
	return result;
}



Java


/*Helper function that returns the numeric value of a Roman alphabet*/
public static int getNumericValue(char c) {
	int result;

	switch(c) {
		case 'I': result = 1; break;
		case 'V': result = 5; break;
		case 'X': result = 10; break;
		case 'L': result = 50; break;
		case 'C': result = 100; break;
		case 'D': result = 500; break;
		case 'M': result = 1000; break;
		default: result = 0; break;
	}
	return result;
}

/* 
Main function that converts a Roman string into an integer
str1: valid input string with Roman alphabets
Return value: integer equivalent of the Roman string
*/
public static int romanToInt(char[] str1) {
	/*Process the string from the rear*/		
	int i = str1.length - 1;
	if (i < 0)
		return 0;

	int result = getNumericValue(str1[i]);
	--i;
	while (i >= 0) {
		int curDigitVal = getNumericValue(str1[i]);
		int nextDigitVal = getNumericValue(str1[i+1]);

		if (curDigitVal < nextDigitVal)
			result -= curDigitVal;
		else
			result += curDigitVal;		
		
		--i;
	}

	return result;
}



Python


#str1: valid input string with Roman alphabets
#Return value: integer equivalent of the Roman string
def roman_to_int(str1) :
	table = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
	
	i = len(str1) – 1 #Process the string from the rear
	if (i < 0):
		return 0

	result = table[str1[i]]
	i -= 1
	while (i >= 0) :
		cur_digit_val = table[str1[i]]
		next_digit_val = table[str1[i+1]]
		if (cur_digit_val < next_digit_val):
			result -= cur_digit_val
		else:
			result += cur_digit_val		
		i -= 1
	
	return result



Print a number in words

© Parineeth M R

Question 26. Given a number from 0 to 999,999,999, print the number in words. So 200,145,700 should be printed as two hundred million one hundred forty five thousand seven hundred


We will break the input number into millions, thousands and the remaining 3 least significant digits. So in this case 200,145,700 gets broken down to 200, 145 and 700. Then we make use of a helper function that prints 3 consecutive digits.

C/C++


/* 
Helper function to print number from 1 to 999
number: number from 1 to 999
*/
void print_3_digits(int number)
{
	int hundreds_digit, tens_digit, unit_digit, remainder;

	/*basic_lookup[0] is empty. We want basic_lookup[1] to map to "One" 
	and so on. */
	char *basic_lookup[] = {"", "One", "Two", "Three", "Four", "Five", "Six",
			"Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", 
			"Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen",
			"Eighteen", "Nineteen"};

	/*tens_lookup[0] and tens_lookup[1] are empty.
	We want tens_lookup[2] to map to "Twenty" and so on. */
	char *tens_lookup[] = {"", "","Twenty", "Thirty", "Fourty", "Fifty", 
			"Sixty", "Seventy", "Eighty", "Ninety"};

	/*Suppose number is 987, then hundreds_digit is 9*/
	hundreds_digit = number / 100;
	if (hundreds_digit > 0) {
		printf("%s Hundred ", basic_lookup[hundreds_digit]);
	}
	
	/*Suppose number is 987, then remainder will be 87*/
	remainder = number % 100;
	if (remainder > 0) {
		if (remainder <= 19) {
			printf("%s ", basic_lookup[remainder]);			
		} else {
			tens_digit = remainder / 10;
			unit_digit = remainder % 10;
			printf("%s ", tens_lookup[tens_digit]);
			printf("%s ", basic_lookup[unit_digit]);
		}
	}
	
}
 
/*
Main function to print the number in words
number: any number from 0 to 999999999
*/
void print_num_in_words(int number)
{
	int millions, thousands, remainder;

	/*If number is 0, handle it here and return*/
	if (number == 0) {
		printf("Zero \n");
		return;
	}

	/*Suppose number is 123456789, then millions = 123, remainder = 456789*/
	millions = number / 1000000;
	remainder = number - (millions * 1000000);
	
	/*Suppose remainder = 456789, then thousands = 456, remainder = 789*/
	thousands = remainder / 1000;
	remainder = remainder - (thousands * 1000);

	if (millions > 0) {
		print_3_digits(millions);
		printf("Million ");
	}

	if (thousands > 0) {
		print_3_digits(thousands);
		printf("Thousand ");
	}

	if (remainder > 0) {
		print_3_digits(remainder);
	} 
	
	printf("\n");
}



Java


/* 
Helper function to print number from 1 to 999
number: number from 1 to 999
*/
public static void print3Digits(int number) {
	/*basicLookup[0] is empty. We want basicLookup[1] to map to "One"
	and so on. */
	String[] basicLookup = {"", "One", "Two", "Three", "Four", "Five", 
			"Six", "Seven", "Eight", "Nine", "Ten", "Eleven", 
			"Twelve", "Thirteen", "Fourteen", "Fifteen", 
			"Sixteen", "Seventeen",	"Eighteen", "Nineteen"};

	/*tensLookup[0] and tensLookup[1] are empty.
	We want tensLookup[2] to map to "Twenty" and so on. */
	String[] tensLookup = {"", "","Twenty", "Thirty", "Fourty", "Fifty",
			"Sixty", "Seventy", "Eighty", "Ninety"};

	/*Suppose number is 987, then hundredsDigit is 9*/
	int hundredsDigit = number / 100;
	if (hundredsDigit > 0) {
		System.out.print(basicLookup[hundredsDigit] + " Hundred ");
	}

	/*Suppose number is 987, then remainder will be 87*/
	int remainder = number % 100;
	if (remainder > 0) {
		if (remainder <= 19) {
			System.out.print(basicLookup[remainder] + " ");			
		} else {
			int tensDigit = remainder / 10;
			int unitDigit = remainder % 10;
			System.out.print(tensLookup[tensDigit] + " ");
			System.out.print(basicLookup[unitDigit] + " ");
		}
	}
}
 
/*
Main function to print the number in words
number: any number from 0 to 999999999
*/
public static void printNumInWords(int number) {
	/*If number is 0, handle it here and return*/
	if (number == 0) {
		System.out.println("Zero ");
		return;
	}

	/*Suppose number is 123456789, then millions = 123, remainder = 456789*/
	int millions = number / 1000000;
	int remainder = number - (millions * 1000000);

	/*Suppose remainder = 456789, then thousands = 456, remainder = 789*/
	int thousands = remainder / 1000;
	remainder = remainder - (thousands * 1000);

	if (millions > 0) {
		print3Digits(millions);
		System.out.print("Million ");
	}

	if (thousands > 0) {
		print3Digits(thousands);
		System.out.print("Thousand ");
	}

	if (remainder > 0) {
		print3Digits(remainder);
	} 

	System.out.println("");
}



Python


#Helper function to print number from 1 to 999
#number: number from 1 to 999
def print_3_digits(number) :
	#basic_lookup[0] is empty. We want basic_lookup[1] to map to 'One'
	#and so on. 
	basic_lookup = ['', 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 
			'Seven', 'Eight', 'Nine', 'Ten', 'Eleven', 'Twelve',
			'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 
			'Seventeen', 'Eighteen', 'Nineteen']

	#tens_lookup[0] and tens_lookup[1] are empty.
	#We want tens_lookup[2] to map to 'Twenty' and so on. 
	tens_lookup = ['', '','Twenty', 'Thirty', 'Fourty', 'Fifty', 'Sixty',
			'Seventy', 'Eighty', 'Ninety']

	#Suppose number is 987, then hundreds_digit is 9
	hundreds_digit = number // 100
	if (hundreds_digit > 0) :
		print(basic_lookup[hundreds_digit] + ' Hundred ', end='')
	

	#Suppose number is 987, then remainder will be 87
	remainder = number % 100
	if (remainder > 0) :
		if (remainder <= 19) :
			print(basic_lookup[remainder] + ' ', end='')
		else :
			tens_digit = remainder // 10
			unit_digit = remainder % 10
			print(tens_lookup[tens_digit] + ' ', end='')
			print(basic_lookup[unit_digit] + ' ', end='')
 
#Main function to print the number in words
#number: any number from 0 to 999999999
def print_num_in_words(number) :
	#If number is 0, handle it here and return
	if (number == 0) :
		print('Zero ')
		return
	
	#Suppose number is 123456789, then millions = 123, remainder = 456789
	millions = number // 1000000
	remainder = number - (millions * 1000000)

	#Suppose remainder = 456789, then thousands = 456, remainder = 789
	thousands = remainder // 1000
	remainder = remainder - (thousands * 1000)

	if (millions > 0) :
		print_3_digits(millions)
		print('Million ', end='')
	
	if (thousands > 0) :
		print_3_digits(thousands)
		print('Thousand ', end='')
	
	if (remainder > 0) :
		print_3_digits(remainder)
	 
	print('')




Convert a string to an integer

© Parineeth M R

Question 25. Convert a string to an integer without using built-in functions


The function for converting a string to an integer is given below:

C/C++


/*
str: string to be converted to an integer
Result: integer value of the string
*/
int function_atoi(const char * str)
{
	int i, length; 
	int val = 0;
	int is_negative = 0;

	if (!str)
		return 0;

	length = strlen(str);
	i = 0;
	if (str[0] == '-') {
		is_negative = 1;
		++i;
	} 

	while (i < length ) {
		if (str[i] >= '0' && str[i] <= '9') {
			val = (val * 10) + (str[i] - '0');
		}
		else {
			break;
		}
		++i;
	}
	
	if (is_negative)
		val = -1 * val;

	return val;
}



Java


/*
str1: string to be converted to integer
result: integer value of string
*/
public static int strToInt(char[] str1) {
	int result = 0;
	boolean isNegative = false;
	int count = 0;
	
	for (char c : str1) {
		if (c == '-' && count == 0)
			isNegative = true;
		
		if ('0' <= c && c <= '9') 
			result = (result * 10) + (c - '0');

		count++; 
	}

	if (isNegative)
		result = -1 * result;

	return result;
}



Python


#str1: string to be converted to integer
#result: integer value of string
def str_to_int(str1):
	result = 0
	count = 0
	is_negative = False

	for c in str1:
		if (c == '-' and count == 0):
			is_negative = True

		if ('0' <= c and c <= '9'):
			result = (result * 10) + (ord(c) - ord('0'))

		count += 1

	if (is_negative):
		result = -1 * result 
		
	return result



Count number of words in a string

© Parineeth M R

Question 24. Count the number of words in a string


We will define a word as a collection of one or more characters from a-z and A-Z. The words in a string can be separated by multiple spaces, tabs, punctuation marks etc. To count the number of words, as we traverse the string we will keep track of the previous character and the current character. If the previous character is not an alphabet from a-z and A-Z and the current character is an alphabet from a-z and A-Z, then we have encountered a new word and we increase the word count by 1.

C/C++


/*
str1: string in which the number of words have to be counted
Return value: number of words in the string
*/
int count_words(char *str1) 
{
	int num_words, pos;
	char cur_char, is_prev_char_alphabet;

	if (!str1)
		return 0;

	num_words = 0;
	pos = 0;
	cur_char = str1[pos];
	is_prev_char_alphabet = 0;
	while (cur_char != '\0') {
		int is_cur_char_alphabet = is_alphabet(cur_char);

		/*If previous character is not an alphabet and current character
		is an alphabet then we have found a new word*/
		if (!is_prev_char_alphabet && is_cur_char_alphabet) {
			++num_words;
		}

		is_prev_char_alphabet = is_cur_char_alphabet;
		
		pos++;
		cur_char = str1[pos];		
	}

	return num_words;
}

/*Helper function which checks if a character is an alphabet(a-zA-Z)*/
int is_alphabet(char c)
{
	if (c >= 'A' && c <= 'Z')
		return 1;

	if (c >= 'a' && c <= 'z')
		return 1;

	return 0;		
}



Java


/*
str1: string in which the number of words have to be counted
Return value: number of words in the string
*/
public static int countWords(char[] str1) {
	if (str1 == null)
		return 0;

	int numWords = 0;
	boolean isPrevCharAlphabet = false;
	for (char c : str1) {
		boolean isCurCharAlphabet = isAlphabet(c);

		/*If previous character is not an alphabet and current character is 
		an alphabet then we have found a new word*/
		if (!isPrevCharAlphabet && isCurCharAlphabet) 
			++numWords;

		isPrevCharAlphabet = isCurCharAlphabet;
	}

	return numWords;
}

/*Helper function which checks if a character is an alphabet(a-zA-Z)*/
public static boolean isAlphabet(char c)	{
	if (c >= 'A' && c <= 'Z')
		return true;

	if (c >= 'a' && c <= 'z')
		return true;

	return false;		
}



Python


#str1: string in which the number of words have to be counted
#Return value: number of words in the string
def count_words(str1) :
	if (str1 == None):
		return 0

	num_words = 0
	is_prev_char_alphabet = False
	for c in str1 :
		is_cur_char_alphabet = is_alphabet(c)

		#If previous character is not an alphabet and current character is 
		#an alphabet then we have found a new word
		if (not is_prev_char_alphabet and is_cur_char_alphabet) :
			num_words += 1
		
		is_prev_char_alphabet = is_cur_char_alphabet
	
	return num_words

#Helper function which checks if a character is an alphabet(a-zA-Z)
def is_alphabet(c):
	if (c >= 'A' and c <= 'Z'):
		return True

	if (c >= 'a' and c <= 'z'):
		return True

	return False



Find if two strings are anagrams

© Parineeth M R

Question 23. Find if two string words are anagrams of each other


Two strings are anagrams of each other if re-arrangement of characters in one string results in the other string. This implies that two string words are anagrams if for each character, the number of times the character occurs in the first string is equal to the number of times it occurs in the second string. The code for finding if two words are anagrams is given below

C/C++


/*str1, str2: the two non-NULL strings which we want to compare
Return value: 1 if the two strings are anagrams, 0 otherwise
*/
int are_strings_anagrams( char *str1, char *str2)
{
	int count1[NUM_CHARACTERS], count2[NUM_CHARACTERS];
	int is_anagram, i;

	/*Initilize the counts to zero */
	memset(count1, 0, sizeof(int) * NUM_CHARACTERS);
	memset(count2, 0, sizeof(int) * NUM_CHARACTERS);
	
	/*Compute the character counts for str1 and str2*/
	while (*str1) {
		count1[(int)*str1]++;
		str1++;
	}
	
	while (*str2) {
		count2[(int)*str2]++;
		str2++;
	}
	
	/*Compare the counts*/
	is_anagram = 1;
	for (i = 0; i < NUM_CHARACTERS; ++i) {
		if (count1[i] != count2[i]) {
			is_anagram = 0;
			break;
		}
	}
	return is_anagram;
}



Java


/*
str1, str2: the two strings which we want to compare
Return value: true if the two strings are anagrams, false otherwise
*/
public static boolean areAnagrams( char[] str1, char[] str2) 	{
	/*Initilize the counts to zero */
	int[] count1 = new int[NUM_CHARACTERS]; //NUM_CHARACTERS is 256
	int[] count2 = new int[NUM_CHARACTERS];

	/*Compute the character counts for str1 and str2*/
	for (char c: str1) 
		count1++;

	for (char c : str2) 
		count2++;

	/*Compare the counts*/
	boolean isAnagram = true;
	for (int i = 0; i < NUM_CHARACTERS; ++i) {
		if (count1[i] != count2[i]) {
			isAnagram = false;
			break;
		}
	}

	return isAnagram;
}



Python


#str1, str2: the two strings which we want to compare
#Return value: True if the two strings are anagrams, False otherwise
def are_anagrams(str1, str2) :	
	count1 = [0] * NUM_CHARACTERS #NUM_CHARACTERS is 256
	count2 = [0] * NUM_CHARACTERS

	#Compute the character counts for str1 and str2
	for  c in str1:
		count1[ord(c)] += 1
	

	for  c in str2:
		count2[ord(c)] += 1
	
	#Compare the counts
	is_anagram = True
	if (count1 != count2):
		is_anagram = False
		
	return is_anagram



Rotate an array

© Parineeth M R

Question 22. Rotate an array by k times


Consider the array {10, 20, 30, 40, 50}. Suppose we rotate the array once, we have to move the elements 10, 20, 30, 40 right by 1 position and move the last element 50 to the beginning to get {50, 10, 20, 30, 40}. So if we have an array of size n, then for 1 rotate operation we will need n moves. If we rotate the array k times then there will be k*n moves. There is a faster method for rotating an array. Let the array be A = {10, 20, 30, 40, 50} and the number of rotations k = 2. The procedure is:

1. Reverse the entire array. So we get {50, 40, 30, 20, 10}

2. Reverse the array in the region 0 to k -1. If k = 2, we reverse the region A[0] to A[1]. So we get the array {40, 50, 30, 20, 10}

3. Finally reverse the array in the region k to n-1 where n is the length of the array. If k=2, we reverse the region A[2] to A[4]. So we get the required result {40, 50, 10, 20, 30}.

With this technique, we always need 2*n moves irrespective of the value of k.

C/C++


/*Main function to rotate a 1 dimensional array
a: array which should be rotated. 
length: number of elements in the array. Should be > 0
num_rotations: how many times to rotate the array. Should be >= 0
*/
void rotate_array(int a[], int length, int num_rotations)
{
	/*Suppose an array has a length of 5, every time we rotate by 5 
	locations, we end up with the same array. So obtain num_rotations 
	value from 0 to length - 1*/
	num_rotations = num_rotations % length;

	if (num_rotations == 0)
		return;

	reverse_array(a, 0, length - 1);

	reverse_array(a, 0, num_rotations - 1);

	reverse_array(a, num_rotations, length - 1);
}



Java


/*Main function to rotate a 1 dimensional array
a: array which should be rotated. 
numRotations: how many times to rotate the array. Should be >= 0
*/
public static void rotateArray(int[] a, int numRotations) {
	int length = a.length;
	if (length == 0)
		return;

	/*Suppose an array has a length of 5, every time we rotate by 
	5 locations, we end up with the same array. So obtain numRotations 
	value from 0 to length - 1*/
	numRotations = numRotations % length;

	if (numRotations == 0)
		return;

	reverseArray(a, 0, length - 1);

	reverseArray(a, 0, numRotations - 1);

	reverseArray(a, numRotations, length - 1);
}



Python


#Main function to rotate a 1 dimensional list
#a: list which should be rotated. 
#num_rotations: how many times to rotate the list. Should be >= 0
def rotate_list(a, num_rotations) :
	length = len(a)
	if (length == 0):
		return

	#Suppose a list has a length of 5, every time we rotate by 
	#5 locations, we end up with the same list. So obtain num_rotations 
	#value from 0 to length - 1
	num_rotations = num_rotations % length

	if (num_rotations == 0):
		return

	reverse_list(a, 0, length - 1)

	reverse_list(a, 0, num_rotations - 1)

	reverse_list(a, num_rotations, length - 1)


#Helper function which reverses a list in region (low, high)
#a: list which needs to be reversed
#low: lower index of region to be reversed
#high: higher index of region to be reversed
def reverse_list(a, low, high) :
	while (low < high) :
		a[low], a[high] = a[high], a[low]
		low += 1
		high = high - 1



Move all zeroes to one end

© Parineeth M R

Question 21. Move all the zeroes in an array to the right end of the array


We can move all the zeroes to one end of the array (in this case, the right end) in O(n) using the following technique:

1. Scan for the first zero from the left side of the array.

2. Scan for the first non-zero from the right side of the array.

3. Swap the zero and non-zero provided that the zero appears to the left of the non-zero

C/C++


/*
a: input array in which the zeroes should be moved to one end
length: number of elements in array a 
*/
void move_zeroes(int a[], int length)
{
	int left, right;

	left = 0;
	right = length - 1;

	while (left < right) {
		/*Locate the first zero from the left*/
		while (left < length && a[left] != 0)
			left++;

		/*Locate first non-zero from the right*/
		while (right >= 0 && a[right] == 0)
			right--;

		if (left < right) {
			/*Swap a[left] and a[right]*/
			int temp = a[left];
			a[left] = a[right];
			a[right] = temp;
		}
	}
} 



Java


/*
a: input array in which the zeroes should be moved to one end
*/
public static void moveZeroes(int[] a) {
	int length = a.length;

	int left = 0;
	int right = length - 1;

	while (left < right) {
		/*Locate the first zero from the left*/
		while (left < length && a[left] != 0)
			left++;

		/*Locate first non-zero from the right*/
		while (right >= 0 && a[right] == 0)
			right--;

		if (left < right) {
			/*Swap a[left] and a[right]*/
			int temp = a[left];
			a[left] = a[right];
			a[right] = temp;
		}
	}
}



Python


#a: input list in which the zeroes should be moved to one end
def move_zeroes(a) :
	length = len(a)

	left = 0
	right = length - 1

	while (left < right) :
		#Locate the first zero from the left
		while (left < length and a[left] != 0):
			left += 1

		#Locate first non-zero from the right
		while (right >= 0 and a[right] == 0):
			right = right - 1

		if (left < right) :
			#Swap a[left] and a[right]
			a[left], a[right] = a[right], a[left]



Remove all duplicates from an array

© Parineeth M R

Question 20. Given an array, remove all the duplicates from the array


Suppose the given array is A = {1, 4, 2, 1, 5, 2} and we have to remove all duplicates from it, then the result array is {1, 4, 2, 5}. All duplicates in an array A can be removed using the following approaches

1. Brute force approach. Pick every element in A and remove all the duplicates of that element. Removing all duplicates of one element can be done in O(n). Since we have to do this for n elements, the time complexity will be O(n2) and no extra space is needed

2. Hash table approach. Traverse the elements in A and add the elements to a hash table. If we encounter an element which is already in the hash table, then we exclude it from the result. The time complexity is O(n) but we will need extra space for the hash table.

3. Sorting. Sort the array A. After sorting, the duplicates will be arranged next to each other. Then iterate through the sorted array and retain an element in A only if it is different from the previous element. We will be using this approach in the code below. The time complexity is O(nlog(n)) and we don’t need additional space.

C/C++


/*
a: non-empty array from which duplicates should be removed. 
	this array will be modified in-place
length: number of elements in array a 
Returns: number of elements in array a after removing duplicates 
*/
int remove_duplicates(int a[], int length)
{
	int i, fill_pos;

	/*Sort the array*/
	sort(a, length);

	fill_pos = 1;
	for (i = 1; i < length; ++i) {
		if (a[i] != a[i - 1]) {
			a[fill_pos] = a[i];
			fill_pos++;
		}
	}

	return fill_pos;
}



Java


/*
a: non-empty input array from which duplicates should be removed. 
	this array will be modified
Returns: new output array which doesn't have duplicates 
*/
public static int[] removeDuplicates(int[] a) {
	int length = a.length;

	/*Sort the array*/
	Arrays.sort(a);

	int fillPos = 1;
	for (int i = 1; i < length; ++i) {
		if (a[i] != a[i - 1]) {
			a[fillPos] = a[i];
			fillPos++;
		}
	}

	int[] result = Arrays.copyOf(a, fillPos);
	return result;
}



Python


#a: non-empty input list from which duplicates should be removed. 
#	this list will be modified in-place
def remove_duplicates(a) :
	length = len(a)

	#Sort the list
	a.sort()

	fill_pos = 1
	for  i in range(1, length):
		if (a[i] != a[i - 1]) :
			a[fill_pos] = a[i]
			fill_pos += 1

	#remove the remaining items in the list from fill_pos onwards
	if (fill_pos < length):		
		del a[fill_pos:]



Remove all occurrences of an element from an array

© Parineeth M R

Question 19. Given an array, remove all occurrences of an element from the array


Suppose the given array is A = {1, 4, 2, 1, 5, 2} and we have to remove all occurences of 1 from it, then the result array is {4, 2, 5, 2}. The element to be removed from the array can be present in multiple locations. We can efficiently remove all occurrences of the element in O(1) space and O(n) time in a single pass through the array by doing the following:

1. Maintain a variable called fill_pos to keep track of where we should store the next element of the array that should not be deleted. Initialize fill_pos to 0.

2. Traverse through the array. If the current element in the array should be deleted then skip it. If current element in the array should not be deleted, then store the current element at fill_pos in the array and increment fill_pos

C/C++


/*
a: input array from which all occurrences of an element should be removed
length: number of elements in array a 
x: element to be removed
Return value: number of elements in a after removing x 
*/
int remove_element(int a[], int length, int x)
{
	int i, fill_pos;

	fill_pos = 0;
	for (i = 0; i < length; ++i) {
		if (a[i] != x) {
			a[fill_pos] = a[i];
			fill_pos++;
		}
	}

	return fill_pos;
}



Java


/*
a: input array from which all occurrences of an element should be removed
x: element to be removed
Return value: output array after removing x 
*/
public static int[] removeElement(int[] a, int x) {
	int fillPos = 0;
	for (int i = 0; i < a.length; ++i) {
		if (a[i] != x) {
			a[fillPos] = a[i];
			fillPos++;
		}
	}

	int[] result = Arrays.copyOf(a, fillPos);
	return result;
}



Python


#a: input list from which all occurrences of an element should be removed
#x: element to be removed
def remove_element(a, x) :
	length = len(a)
	fill_pos = 0
	for  i in range(0, length):
		if (a[i] != x) :
			a[fill_pos] = a[i]
			fill_pos += 1
	
	#delete all the elements from fill_pos onwards	
	if (fill_pos < length) :
		del a[fill_pos:]



Replace each element with next greatest

© Parineeth M R

Question 18. Replace each element in an array with the next greatest


Consider the array A = {0, 2, 8, 1, 3, 5, 4}.

The greatest number after 0 in A is maximum of {2, 8, 1, 3, 5, 4} = 8. So 0 is replaced by 8.

The greatest number after 8 in A is maximum of {1, 3, 5, 4} = 5. So 8 is replaced with 5.

4 is the last number in A. There are no more elements to its right. So 4 is replaced by an invalid number or the smallest possible number.

So the resulting array is = {8, 8, 5, 5, 5, 4, INVALID_NUMBER}.

The brute force approach will try to compute the next greatest of an element by scanning all the elements to its right. This will have a time complexity of O(n2).

However we can achieve the same in O(n) by traversing from the end of the array to the beginning and maintaining the maximum element seen so far. The code is given below

C/C++


/*
a: array in which each element should be replaced with next greatest
n: number of elements in the array. n >= 1
*/
void replace_with_next_greatest(int a[], int n) {
	int i, next_greatest, temp;

	next_greatest = a[n-1];
	a[n-1] = INVALID_NUMBER;  

	/*Process the array from backwards*/
	for (i = n-2; i >= 0; --i) {
		temp = a[i];

		a[i] = next_greatest;

		if (temp > next_greatest)
			next_greatest = temp;
	}
}



Java


/*
a: non-empty array in which each element should be replaced with next greatest
*/
public static void replaceWithNextGreatest(int[] a) {
	int n = a.length;
	int nextGreatest = a[n-1];
	a[n-1] = INVALID_NUMBER;  

	/*Process the array backwards*/
	for (int i = n-2; i >= 0; --i) {
		int temp = a[i];

		a[i] = nextGreatest;

		if (temp > nextGreatest)
			nextGreatest = temp;
	}
}



Python


#a: non-empty list in which each element should be replaced with next greatest
def replace_with_next_greatest(a) :
	n = len(a)

	next_greatest = a[n-1]
	a[n-1] = INVALID_NUMBER  

	#Process the list from the back
	for i in range(n-2, -1, -1) :
		temp = a[i]

		a[i] = next_greatest

		if (temp > next_greatest):
			next_greatest = temp