CoreJava – Arrays – Assignment - 1

Core Java – Arrays – Assignment - 1

 

1.       Write a program that takes an array of integers and finds the sum of all the elements at odd indices.

Algorithm:

·         Initialize a variable sum to 0.

·         Iterate over the array starting at index 1 (i.e. the second element).

·         For each odd index, add the element to sum.

·         Return sum.

 

2.       Write a program that takes an array of strings and finds the longest string.

Algorithm:

·         Initialize a variable longest to an empty string.

·         Iterate over the array.

·         For each string, compare its length to the length of longest.

·         If the current string is longer than longest, update longest.

·         Return longest.

 

3.       Write a program that takes an array of integers and finds the index of the first occurrence of a given number.

Algorithm:

·         Iterate over the array.

·         For each element, compare it to the given number.

·         If the element is equal to the given number, return its index.

·         If no match is found, return -1.

 

4.       Write a program that takes an array of integers and removes all the negative numbers.

Algorithm:

·         Create a new array of the same length as the original array.

·         Initialize a variable count to 0.

·         Iterate over the array.

·         For each element, check if it is non-negative.

·         If it is, add it to the new array and increment count.

·         Return a new array of length count.

 

5.       Write a program that takes an array of integers and finds the two elements whose sum is closest to zero.

Algorithm:

·         Sort the array in ascending order.

·         Initialize variables left and right to the first and last indices of the array.

·         Initialize a variable minSum to the sum of the first two elements of the sorted array.

·         Iterate over the array.

·         For each element, calculate the sum of the current element and the element at right.

·         If this sum is closer to zero than minSum, update minSum and store the current indices in left and right.

·         If the sum is negative, decrement right. If it is positive, increment left.

·         Return the two elements at indices left and right.

 

6.       Write a program that takes an array of integers and finds the maximum product of any three elements.

Algorithm:

·         Sort the array in ascending order.

·         Initialize a variable n to the length of the array.

·         Calculate the product of the last three elements of the sorted array.

·         Calculate the product of the first two elements and the last element of the sorted array.

·         Return the maximum of these two products.

 

7.       Write a program that takes an array of integers and finds the number of distinct pairs of elements whose sum is equal to a given number.

Algorithm:

·         Initialize a variable count to 0.

·         Create a hash set to store the elements of the array.

·         Iterate over the array.

·         For each element, check if the set contains the difference between the given number and the current element.

·         If it does, increment count.

·         Add the current element to the set.

·         Return count.

 

8.       Write a program that takes an array of integers and finds the length of the longest subarray with consecutive elements.

Algorithm:

·         Create a hash set to store the elements of the array.

·         Initialize a variable maxLength to 0.

·         Iterate over the array.

·         For each element, check if it is the start of a subarray.

·         If it is, iterate over consecutive elements until an element is missing or the end of the array is reached.

·         If the length of this subarray is greater than maxLength, update maxLength.

·         Add all the elements of the subarray to the set.

·         Return maxLength.

 

9.       Write a program that takes an array of integers and finds the minimum and maximum elements with the minimum number of comparisons.

Algorithm:

·         Initialize variables min and max to the first element of the array.

·         Iterate over the array starting at index 1 (i.e. the second element).

·         For each element, compare it to min and max.

·         If it is smaller than min, update min.

·         If it is larger than max, update max.

·         Return min and max.

 

10.   Write a program that takes an array of integers and finds the length of the longest subarray with an equal number of even and odd elements.

Algorithm:

·         Create a hash map to store the difference between the number of even and odd elements.

·         Initialize a variable maxLength to 0.

·         Initialize a variable diff to 0.

·         Iterate over the array.

·         For each element, update diff by adding 1 if it is even and subtracting 1 if it is odd.

·         If diff is 0, update maxLength to the current index plus 1.

·         If diff is already in the map, update maxLength to the maximum of the current index minus the value in the map and the current value of maxLength.

·         Otherwise, add diff to the map with the current index as its value.

·         Return maxLength.

 

11.   Write a program that takes two sorted arrays of integers and finds the median of the combined array.

Algorithm:

·         Initialize variables m and n to the lengths of the two arrays.

·         If m is greater than n, swap the arrays and their lengths.

·         Initialize variables imin and imax to 0 and m, respectively.

·         Iterate over the smaller array.

·         For each element, calculate the index where it would be in the combined array.

·         Use binary search to find the corresponding index in the larger array.

·         Calculate the median of the combined array based on the indices of the two elements in the middle. urn the median.

 

12.   Write a program that takes an array of integers and finds the number of inversions.

Algorithm:

·         Initialize a variable count to 0.

·         Use a modified merge sort to sort the array and count the number of inversions.

·         The modified merge sort should also update count when elements from the right subarray are copied to the merged array before elements from the left subarray.

·         Return count.

 

13.   Write a program that takes an array of integers and finds the maximum sum subarray.

Algorithm:

·         Initialize variables maxSoFar and maxEndingHere to 0.

·         Iterate over the array.

·         For each element, add it to maxEndingHere.

·         If maxEndingHere is negative, set it to 0.

·         If maxEndingHere is greater than maxSoFar, update maxSoFar.

·         Return maxSoFar.

 

14.   Write a program that takes an array of integers and finds the maximum product subarray.

Algorithm:

·         Initialize variables maxSoFar and maxEndingHere to 1 and minEndingHere to 1.

·         Initialize a variable maxProduct to the first element of the array.

·         Iterate over the array.

·         For each element, calculate maxEndingHere and minEndingHere.

·         If the element is negative, swap maxEndingHere and minEndingHere.

·         If maxEndingHere is greater than maxSoFar, update maxSoFar.

·         If the element is 0, reset maxEndingHere and minEndingHere to 1.

·         Multiply the element by maxEndingHere and minEndingHere.

·         If the result is greater than maxProduct, update maxProduct.

·         Return maxProduct.

 

15.   Write a program that takes an array of integers and finds the number of triangles that can be formed from the array elements.

Algorithm:

·         Sort the array.

·         Initialize a variable count to 0.

·         Iterate over the array.

·         For each element, use two pointers to find the number of pairs of elements that can form a triangle with the current element.

·         Add this number to count.

·         Return count.

 

16.   Write a program that takes an array of integers and finds the length of the longest increasing subsequence.

Algorithm:

·         Initialize an array dp of length equal to the length of the input array, with each element initially set to

·         Iterate over the input array starting at index 1.

·         For each element, iterate over the previous elements.

·         If a previous element is less than the current element, update dp with the maximum value of its current value and the value of the previous element in dp plus 1.

·         Return the maximum value in dp.

 

17.   Write a program that takes two sorted arrays of integers and merges them into a single sorted array.

Algorithm:

·         Initialize an array result of length equal to the sum of the lengths of the two input arrays.

·         Initialize variables i, j, and k to 0.

·         Iterate over the arrays.

·         For each pair of elements, add the smaller element to result and increment the corresponding index variable.

·         If one array is exhausted, add the remaining elements of the other array to result.

·         Return result.

 

18.   Write a program that takes an array of integers and finds the number of subarrays whose sum is divisible by a given integer k.

Algorithm:

·         Initialize a dictionary count with a single entry (0, 1).

·         Initialize variables prefixSum and result to 0.

·         Iterate over the array.

·         For each element, update prefixSum to be the sum of the current element and the previous prefixSum.

·         Calculate mod as prefixSum % k.

·         If mod is negative, add k to it.

·         If mod is in count, add count[mod] to result.

·         Increment count[mod] by 1.

·         Return result.

 

19.   Write a program that takes an array of integers and returns an array of the same length, where each element is the product of all the elements in the input array except the element at the corresponding index.

Algorithm:

 

·         Initialize an array result of the same length as the input array.

·         Initialize variables productSoFar and i to 1.

·         Iterate over the input array from left to right.

·         For each element, set result[i] to productSoFar and update productSoFar as the product of itself and the current element.

·         Initialize productSoFar to 1 and iterate over the input array from right to left.

·         For each element, multiply result[i] by productSoFar and update productSoFar as the product of itself and the current element.

·         Return result.

 

20.   Write a program that takes an array of integers and returns an array of the same length, where each element is the product of all the elements in the input array except the element at the corresponding index. The program should use constant space.

Algorithm:

·         Initialize variables productSoFar and i to 1.

·         Initialize an array result of the same length as the input array.

·         Iterate over the input array from left to right.

·         For each element, set result[i] to productSoFar and update productSoFar as the product of itself and the current element.

·         Initialize productSoFar to 1 and iterate over the input array from right to left.

·         For each element, multiply result[i] by productSoFar and update productSoFar as the product of itself and the current element.

·         Return result.

 

21.   Write a program that takes an array of integers and returns the maximum sum of any contiguous subarray.

Algorithm:

·         Initialize variables maxSoFar and maxEndingHere to the first element of the array.

·         Iterate over the array starting at the second element.

·         For each element, calculate maxEndingHere as the maximum of the current element and the sum of the current element and maxEndingHere.

·         Update maxSoFar as the maximum of maxSoFar and maxEndingHere.

·         Return maxSoFar.

 

22.   Write a program that takes an array of integers and returns the maximum product of any contiguous subarray.

Algorithm:

·         Initialize variables maxSoFar and minSoFar to the first element of the array.

·         Initialize result to maxSoFar.

·         Iterate over the array starting at the second element.

·         For each element, calculate maxEndingHere as the maximum of the current element, the current element times maxSoFar, and the current element times minSoFar.

·         Calculate minEndingHere as the minimum of the current element, the current element times maxSoFar, and the current element times minSoFar.

·         Update result as the maximum of result and maxEndingHere.

 

·         Update maxSoFar as maxEndingHere.

·         Update minSoFar as minEndingHere.

·         Return result.

 

23.   Write a program that takes an array of integers and returns the maximum sum of any non-contiguous subarray.

Algorithm:

·         Initialize variables incl and excl to 0.

·         Iterate over the array.

·         For each element, calculate newExcl as the maximum of incl and excl.

·         Update incl as the sum of excl and the current element.

·         Update excl as newExcl.

·         Return the maximum of incl and excl.

 

24.   Write a program that takes an array of integers and returns the length of the longest increasing subsequence.

Algorithm:

·         Initialize an array dp of the same length as the input array, all initialized to 1.

·         Initialize a variable result to 1.

·         Iterate over the input array from left to right.

·         For each element, iterate over the input array from the start up to the current index.

·         For each previous element, if it is less than the current element, update dp[current] as the maximum of itself and dp[previous] + 1.

·         Update result as the maximum of result and dp[current].

·         Return result.

 

25.   Write a program that takes two sorted arrays of integers and merges them into a single sorted array.

Algorithm:

·         Initialize variables i, j, and k to 0.

·         Initialize an empty array result of length equal to the sum of the lengths of the two input arrays.

·         Iterate over both input arrays in parallel.

·         For each element, compare the current element of each array.

·         If the current element of the first array is less than or equal to the current element of the second array, add the current element of the first array to result and increment i.

·         If the current element of the second array is less than the current element of the first array, add the current element of the second array to result and increment j.

·         If either i or j is equal to the length of its corresponding input array, append the remaining elements of the other input array to result.

·         Return result.

 

26.   Write a program that takes an array of integers and an integer k and returns the kth largest element.

Algorithm:

·         Create a priority queue of integers.

·         Iterate over the input array and add each element to the priority queue.

·         Remove elements from the priority queue until the size of the priority queue is equal to k.

·         Return the element at the front of the priority queue.

 

27.   Write a program that takes an array of integers and returns the length of the longest consecutive subsequence.

Algorithm:

 

·         Create a set set and add all the elements of the input array to it.

·         Initialize a variable result to 0.

·         Iterate over the input array.

·         For each element, if it is the start of a sequence (i.e., it is not present in set-1), iterate over the consecutive elements and increment a counter until the end of the sequence is reached (i.e., the next element is not in set).

·         Update result as the maximum of result and the counter.

·         Return result.

 

28.   Write a program that takes two arrays of integers and returns their intersection.

Algorithm:

·         Create a set set1 and add all the elements of the first input array to it.

·         Create a set set2 and add all the elements of the second input array to it.

·         Create an empty set result.

·         Iterate over the elements of set1.

·         For each element, if it is also in set2, add it to result.

·         Return result.

 

29.   Write a program that takes an array of integers and returns a boolean indicating whether there are any three elements that sum to zero.

Algorithm:

·         Sort the input array.

·         Iterate over the input array.

·         For each element, initialize variables left and right to the elements to the right of the current element.

·         While left is less than right:

·         Calculate sum as the sum of the current element, left, and right.

o   If sum is less than 0, increment left.

o   If sum is greater than 0, decrement right.

o   If sum is equal to 0, return true.

o   If no such triplet is found, return false.

 

30.   Write a program that takes an array of integers and a target sum, and returns a boolean indicating whether there are any two elements in the array that sum to the target.

Algorithm:

·         Create a set set and add the first element of the input array to it.

·         Iterate over the remaining elements of the input array.

·         For each element, calculate complement as the target sum minus the current element.

·         If complement is in set, return true.

·         Otherwise, add the current element to set.

·         If no such pair is found, return false.

 

31.   Write a program that takes an array of integers and returns the minimum difference between any two elements.

Algorithm:

·         Sort the input array.

·         Initialize a variable minDiff to the maximum possible integer value.

·         Iterate over the input array.

·         For each element, calculate the absolute difference with the previous element.

·         Update minDiff as the minimum of minDiff and the calculated difference.

 

·         Return minDiff.

 

32.   Write a program that takes an array of integers and returns the maximum sum of any contiguous subarray.

Algorithm:

·         Initialize variables maxSoFar and maxEndingHere to the first element of the input array.

·         Iterate over the remaining elements of the input array.

·         For each element, calculate maxEndingHere as the maximum of the current element and the sum of the current element and maxEndingHere.

·         Update maxSoFar as the maximum of maxSoFar and maxEndingHere.

·         Return maxSoFar.

 

33.   Write a program that takes an array of integers and returns the maximum product of any three elements.

Algorithm:

·         Sort the input array.

·         Initialize a variable n to the length of the input array.

·         Calculate product1 as the product of the first three elements of the sorted array.

·         Calculate product2 as the product of the last two elements and the first element of the sorted array.

·         Return the maximum of product1 and product2.

 

34.   Write a program that takes an array of integers and returns the maximum product of any two elements.

Algorithm:

·         Initialize variables max1, max2, min1, and min2 to the first two elements of the input array.

·         Iterate over the remaining elements of the input array.

·         For each element, update max2 as the maximum of max2 and the product of the current element and max1.

·         Update max1 as the maximum of max1 and the current element.

·         Update min2 as the minimum of min2 and the product of the current element and min1.

·         Update min1 as the minimum of min1 and the current element.

·         Return the maximum of max1 * max2 and min1 * min2.

 

35.   Write a program that takes an array of integers and returns the minimum product of any two elements.

Algorithm:

·         Initialize variables min1 and min2 to the first two elements of the input array.

·         Initialize variables max1 and max2 to the last two elements of the input array.

·         Iterate over the remaining elements of the input array.

·         For each element, update max2 as the maximum of max2 and the product of the current element and max1.

·         Update max1 as the maximum of max1 and the current element.

·         Update min2 as the minimum of min2 and the product of the current element and min1.

·         Update min1 as the minimum of min1 and the current element.

·         Return the minimum of `max1 * max2