Problems Involving Sequences
Contents
- 1 Problems with Sequences
- 1.1 Problems with sequences (no arrays needed)
- 1.1.1 Even Elements
- 1.1.2 Signed Elements
- 1.1.3 Sum and Product
- 1.1.4 Find Element
- 1.1.5 Indices and Elements
- 1.1.6 Increasing Sequence
- 1.1.7 Maximum and minimum
- 1.1.8 Fibonacci numbers
- 1.1.9 Monotonic Sequence
- 1.1.10 Identical Numbers
- 1.1.11 Adding fractions
- 1.1.12 Word Counting
- 1.1.13 Rotating Sequence ^{h}
- 1.1.14 Rotating Monotonic Sequence ^{h}
- 1.1.15 Bitonic Sequence ^{h}
- 1.1.16 Rotating Bitonic Sequence ^{h}
- 1.1.17 Brackets ^{h}
- 1.1 Problems with sequences (no arrays needed)
Problems with Sequences
This is a small list of exercises involving sequences of numbers, for beginners. They do not require storage, thus they have solutions without using arrays.
Problems with sequences (no arrays needed)
Even Elements
How many even elements are in a sequence of n
integer numbers?
Signed Elements
How many negative, zero, and positive elements does a sequence of n
numbers contain?
Sum and Product
Compute the sum and the product of numbers 1
to n
, n
given. Is there a complexity difference between the best algorithms you can find for the two?
Find Element
Given a number a
and a sequence of n
elements, on what position does a
appear in the sequence?
Indices and Elements
How many numbers in a sequence of n
elements are equal to the position in which they appear in the sequence?
Increasing Sequence
Are the numbers in a sequence in increasing order?
Maximum and minimum
Compute the maximum and the minimum value in a sequence of n
numbers.
Fibonacci numbers
Compute the n^{th}
number in the Fibonacci sequence. The Fibonacci sequence has f_{1} = 0
, f_{2} = 1
and f_{n} = f_{n-1} + f_{n-2}
. Example: 0 1 1 2 3 5 8 13 21 ...
Monotonic Sequence
Is a sequence of numbers monotonic? We define a monotonic sequence as a sequence whose numbers are either in increasing order, or in decreasing order.
Identical Numbers
What is the maximum number of consecutive identical numbers in a sequence of n
elements?
Adding fractions
Given a sequence of numbers a_{1} a_{2} ... a_{n}
compute the summation
Word Counting
How many groups of consecutive non-zero numbers are in a sequence? Consider such groups as words, zero being a divider such as space.
Rotating Sequence ^{h}
Let's define a rotating increasing sequence as a sequence of numbers that is either in increasing order, or can be transformed into one by successive rotations (the last element becomes first). Problem: is a sequence of n
numbers a rotating increasing sequence?
Rotating Monotonic Sequence ^{h}
Same as before we define a rotating monotonic sequence as a sequence that is either monotonic, or can be made into one by rotations. Problem: is a sequence of n
numbers a rotating monotonic sequence?
Bitonic Sequence ^{h}
Is a sequence of numbers bitonic? We define a bitonic sequence as a sequence whose numbers are begin in increasing order, and then start decreasing and remain decreasing until the end of the sequence. Increasing and decreasing sequences are also bitonic sequences (that is, it's allowed to skip one of the two sections).
Rotating Bitonic Sequence ^{h}
Same as before we define a rotating bitonic sequence as a sequence that is either bitonic, or can be made into one by rotations. Problem: is a sequence of n
numbers a rotating bitonic sequence?
Brackets ^{h}
Given a sequence of 0
and 1
, where 0
means open bracket and 1
means close bracket, find out if the sequence represents a correct sequence of brackets, and if so, compute the maximum number of nested brackets. Example: 0 1 0 0 1 0 1 1
is correct and has a maximum nesting factor of 2, while 0 0 1 1 1 0
is incorrect.
Legend:
- ^{h} means hard. The problem is difficult.