Problems Involving Arrays
Contents
- 1 Problems with Arrays
- 1.1 Problems with arrays
- 1.1.1 Array Sum
- 1.1.2 Search Array
- 1.1.3 Minimum, Maximum
- 1.1.4 Minimum, Maximum Multiple
- 1.1.5 Insert in Array
- 1.1.6 Delete from Array
- 1.1.7 Reverse Array
- 1.1.8 Rotate Array
- 1.1.9 Rotate Array Multiple ^{h}
- 1.1.10 Binary Search
- 1.1.11 Prime Numbers Generation
- 1.1.12 Select Sort
- 1.1.13 Insert Sort
- 1.1.14 Moving Zeroes
- 1.1.15 Set Array
- 1.1.16 GCD on Array
- 1.1.17 Conversion to another base
- 1.1.18 Eval Poly
- 1.1.19 Substring Search ^{h}
- 1.1.20 Counting Overlaps ^{h}
- 1.1.21 Array Comparison
- 1.1.22 Set operations
- 1.1.23 Sorted Sets Operations
- 1.1.24 Bit Sets Operations
- 1.1.25 Merge Arrays
- 1.1.26 Big Number Addition, Subtraction, Multiplication
- 1.1.27 Selection ^{h}
- 1.1.28 Quicksort ^{h}
- 1.1.29 Merge Sort
- 1.1.30 Bicriterial Sort
- 1.1.31 Majority Element ^{h}
- 1.1 Problems with arrays
Problems with Arrays
This is a small list of exercises involving sequences of numbers, for beginners. However, they require storage, thus they have solutions using arrays. Some of the very introductory problems may be solved without using arrays. They are here to familiarize you with arrays, so solve them using arrays, please.
Problems with arrays
Array Sum
Calculate the sum of all elements in an array.
Search Array
Given an array with n
elements and an extra element e
find the index in the array where element e
appears first.
Minimum, Maximum
Find the value and position of the minimum and maximum elements of an array. For extra credit do it with 3 * n / 2
comparisons (worst case).
Minimum, Maximum Multiple
Find the value of the minimum and maximum elements in an array and the number of times they appear. Try to solve it using just one pass over the array.
Insert in Array
Given an array of n
integers, another integer e
and a position k
, insert integer e
in the array at position k
.
Delete from Array
Given an array of n
integers and a position k
delete element at position k
.
Reverse Array
Given an array with n
elements reverse the order of elements. That means change the order of the elements in the array such that the last element is now first, the second to last is now second, and so on.
Rotate Array
Given an array with n
elements, rotate the array to the left by one position. That means that, in the end, the second element should be the first, the third should be the second, and so on. The first element goes to the last position. Example: [1, 6, 2, 7, 4, 3, 2] goes to [6, 2, 7, 4, 3, 2, 1]
.
Rotate Array Multiple ^{h}
The same problem, but you have to rotate the array by k positions. The problem is hard(ish) when solved without an additional array and in linear time.
Binary Search
Given an array of numbers sorted in ascending order find the position of a given element.
Prime Numbers Generation
Given a positive integer n
generate and display all prime numbers less than or equal to n
.
Select Sort
Given an array of n
numbers sort the array using selection. Sorting means that in the end the numbers should be in ascending order in the array. Using selection means going through the array, finding the maximum number, then swapping the maximum with the last element. Then reiterate with the array minus the last element. Repeat with smaller and smaller parts of the array.
Insert Sort
Sort an array using insertion. Take second element and insert it in A[1..1]
, making A[1..2]
sorted. Then insert third element in A[1..2]
. Keep inserting element on position k
into sorted array A[1..k-1]
up to k = n
.
Moving Zeroes
Change an array of integers such that in the end all zero elements are the last ones in the array.
Set Array
Change an array into a Set array. Meaning, eliminate all duplicates, in place, without using another array.
GCD on Array
Compute the GCD (greatest common divider) of all elements in an array.
Conversion to another base
Given number n
and base b, 1 < b < 17
, convert and display its conversion to base b
.
Eval Poly
Given a polynomial stored in an array, least significant coefficent first, and a number x
evaluate the value of the polynomial in point x
.
Substring Search ^{h}
Given two arrays, s
(search array) and p
(pattern array) find out how many time p appears in s. For instance, if s = [1, 2, 1, 2, 1, 3, 1, 2, 1]
and p = [1, 2, 1]
then p
appears three times in s. The problem is hard only when solved in linear time.
Counting Overlaps ^{h}
Given two bracelets made of n
black and white beads each, find the number of overlaps bead to bead such that overlapping beads have the same color. You can rotate the bracelets when setting them on top of each other. The problem is only hard when solved in linear time.
Array Comparison
Given two arrays of different length find their lexicographical order (meaning which one should appear first in the dictionary).
Set operations
Do the basic operations on sets: intersection, union, difference. Sets are stored as arrays with unique elements, in no particular order.
Sorted Sets Operations
The same requirement as the previous exercise, but this time the sets are stored as arrays with unique sorted elements
Bit Sets Operations
The same requirement as the previous exercise, but this time the sets are stored as arrays with binary elements. Array[i] is 1 if element i is part of the set, 0 otherwise.
Merge Arrays
Given two sorted arrays, build a third sorted array consisting of all the elements in the first two arrays. Duplicates are allowed.
Big Number Addition, Subtraction, Multiplication
Given two big numbers stored as arrays, one decimal digit per element, compute the sum, difference and product of these numbers.
Selection ^{h}
Given an array and a position in the array find the number that sits in that position when the array is sorted. The problem is hard when solved in worst case linear time.
Quicksort ^{h}
Sort an array using Quicksort method. Considered hard because it needs recursion.
Merge Sort
Sort an array using Merge Sort method.
Bicriterial Sort
Given two arrays of integers, E
and W
, where E[i]
is just a number and W[i]
is the weight of E[i]
, sort the arrays such that numbers in E are in ascending order and if two numbers in E are equal then the one with higher weight should come first.
Majority Element ^{h}
A majority element in an array a[] of size n is an element that appears more than n/2 times (and hence there is at most one such element). Given an array find if it has a majority element. The problem is somewhat hard when solved in linear time.
Legend:
- ^{h} means hard. The problem is difficult.