Coding: Arrays

1. Given the following prototype:

int compact(int * p, int size);

write a function that will take a sorted array, possibly with duplicates, and compact the array, returning the new length of the array. That is, if p points to an array containing: 1, 3, 7, 7, 8, 9, 9, 9, 10, when the function returns, the contents of p should be: 1, 3, 7, 8, 9, 10, with a length of 5 returned.
Solution in comment.

48. Given an array of integers, find the contiguous sub-array with the largest sum.

ANS. Can be done in O(n) time and O(1) extra space. Scan array from 1 to n. Remember the best sub-array seen so far and the best sub-array ending in i.
Link to original, 48

49.Given an array of length N containing integers between 1 and N, determine if it contains any duplicates.

ANS. [Is there an O(n) time solution that uses only O(1) extra space and does not destroy the original array?]

53. An array of characters. Reverse the order of words in it.

ANS. Write a routine to reverse a character array. Now call it for the given array and for each word in it.