23. TASK - NOTES - SOLUTION
Note: the task uses the European (German) note names, where the tone H corresponds to the English tone B.
Solution using arrays and linear search
The solution is shown below:#include <iostream>
using namespace std;
/*
In music, tones are arranged in octaves, each consisting of 7 basic tones (the white keys on a piano)
and 5 raised/lowered tones (the black keys on a piano). The basic tones are C, D, E, F, G, A, H (in English
notation H is called B), while the raised/lowered tones are between C and D (the tone C# i.e. D♭), between
D and E (the tone D# i.e. E♭), between F and G (the tone F# i.e. G♭), between G and A (the tone G# i.e. A♭)
and between A and H (the tone A# i.e. H♭, which is sometimes also marked B). Let us agree to mark all
in-between tones as raised (using the symbol #). Then all the tones are arranged like this:
C, C#, D, D#, E, F, F#, G, G#, A, A#, H, C, C#, D, D#, E, F, ....
Transposing a melody means moving it a certain number of tones up or down. Write a
program that transposes the entered melody, i.e. the entered sequence of tones.
Input
A string of at most 1000 characters containing the sequence of tones to be transposed is read from
standard input, followed by a number between -11 and 11 that tells by how many tones the sequence
should be transposed.
Output
Print the transposed sequence of tones to standard output.
Example 1
Input
GDGHDCAF#D
5
Output
CGCEGFDHG
Explanation
Moving from the tone G by 5 places to the right in the order
C, C#, D, D#, E, F, F#, G, G#, A, A#, H, C, C#, D, D#, E, F, ....
gives the tone C. Moving from the tone D by 5 places to the right gives the tone G, etc.
Example 2
Input
C#F#AG
-3
Output
A#D#F#E
*/
int find_note(int notesSize, string note, string notes[]) {
// Search
for (int i = 0; i < notesSize; i++) {
if (notes[i] == note) {
return i; // found
}
}
return -1; // not found
}
int main() {
string notes[] = {"C", "C#", "D", "D#", "E", "F", "F#", "G", "G#", "A", "A#", "H"};
int length = sizeof(notes) / sizeof(string);
string melody;
int shift;
cin >> melody;
cin >> shift;
for (int i = 0; i < melody.length(); i++) {
string note;
if (i + 1 < melody.size() && melody.substr(i + 1, 1) == "#") {
note = melody.substr(i, 2); // take the raised tone as well
i++; // move by one additional character
} else {
note = melody.substr(i, 1); // take the basic tone
}
int pos = find_note(length, note, notes);
if (pos != -1) {
int newPos = (pos + length + shift) % length; // transpose the tone
cout << notes[newPos]; // print the transposed tone
} else {
cout << note; // if the tone is not found, print it directly (or you can handle the error)
}
}
cout << endl; // new line after transposing
return 0;
}First, an array of strings representing the notes is created. The user enters the melody as a string and the shift as an int. The melody contains notes that the program has to recognize. Inside the for loop, a note is extracted as a substring of length 1, or a substring of length 2 if the note contains the character "#". For the extracted note, its current position in the array of strings notes is found, and for this search a separate function called "find_note" is created, which returns the position of the current note or, if it does not find it, returns the value "-1".The search here uses the linear search algorithm, which will not be efficient enough for an array with a large amount of data.
To find the new position, we need to add the shift, whose value can also be a negative integer (moving "to the left").
If the shift + old position is greater than the length of the array, counting continues from the beginning of the array. Likewise, if the position is moved to the left side of the array, after the position whose value is 0, counting continues from the end of the array to the left. This can be done with the operator for computing the modulo of an integer "%" in the following way:
new_position = (old_position + shift) % array_length
To improve the solution by using binary search instead of linear search, the array we search in must be sorted. The tones are listed in the order of the octave, but not alphabetically ("A" and "A#" come before "C" in alphabetical order), so we search in a sorted copy of the array, which also remembers the position of every tone in the octave. After that, we can implement a function for binary search that finds the positions of the tones more efficiently.
- Linear vs. binary search: The original solution uses linear search, which is enough for a small number of tones, but it can be improved by using binary search over a sorted array of tones. This improves efficiency, especially for larger arrays.
- Modulo operator: It is important to point out that the modulo operation in the formula (pos + shift + length) % length makes it possible to handle the shift correctly, even for negative values, making sure that the transposition goes back to the beginning of the array if needed.
Here is how this can look:
Solution using arrays and binary search
#include <iostream>
#include <string>
#include <algorithm> // for std::lower_bound and std::sort
#include <utility> // for std::pair
using namespace std;
// 17.11.2026 – binary search needs an alphabetically sorted array, so we search
// in a sorted copy of pairs (name of the tone, position in the octave)
int find_note(int notesSize, const string& note, const pair<string, int> sortedNotes[]) {
// Binary search is used
const pair<string, int>* found = lower_bound(sortedNotes, sortedNotes + notesSize, make_pair(note, -1));
if (found != sortedNotes + notesSize && found->first == note) {
return found->second; // found - return the position of the tone in the octave
}
return -1; // not found
}
int main() {
string notes[] = {"C", "C#", "D", "D#", "E", "F", "F#", "G", "G#", "A", "A#", "H"};
int length = sizeof(notes) / sizeof(string);
// Sorted copy: A, A#, C, C#, D, D#, E, F, F#, G, G#, H
pair<string, int> sortedNotes[12];
for (int i = 0; i < length; i++) {
sortedNotes[i] = make_pair(notes[i], i);
}
sort(sortedNotes, sortedNotes + length);
string melody;
int shift;
cin >> melody;
cin >> shift;
for (int i = 0; i < melody.length(); i++) {
string note;
if (i + 1 < melody.size() && melody.substr(i + 1, 1) == "#") {
note = melody.substr(i, 2); // take the raised tone as well
i++; // move by one additional character
} else {
note = melody.substr(i, 1); // take the basic tone
}
int pos = find_note(length, note, sortedNotes);
if (pos != -1) {
int newPos = (pos + length + shift) % length; // transpose the tone
cout << notes[newPos]; // print the transposed tone
} else {
cout << note; // if the tone is not found, print it directly (or you can handle the error)
}
}
cout << endl; // new line after transposing
return 0;
}Moving from a static array to vectors brings several advantages. First, vectors in C++ manage their size automatically, which allows more flexible handling of data. Also, the function find from the STL offers a simpler way of searching for tones than manually searching a static array. Using the modulo operator (pos + shift + length) % length, we enable cyclic movement through the tones, making sure that even for transpositions that go beyond the bounds of the array, the tones correctly rotate back to the beginning. The task can also be solved using vectors, which is an improved version of the solution:Solution using vectors
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<string> notes = {"C", "C#", "D", "D#", "E", "F", "F#", "G", "G#", "A", "A#", "H"};
string melody;
int shift;
cin >> melody;
cin >> shift;
for (int i = 0; i < melody.length(); i++) {
string note;
if (i + 1 < melody.length() && melody.substr(i + 1, 1) == "#") {
note = melody.substr(i, 2); // take the raised tone
i++; // move by one additional character
} else {
note = melody.substr(i, 1); // take the basic tone
}
auto it = find(notes.begin(), notes.end(), note);
if (it != notes.end()) {
int pos = it - notes.begin();
int newPos = (pos + shift + notes.size()) % notes.size(); // transpose the tone
cout << notes[newPos]; // print the transposed tone
} else {
cout << note; // if the tone is not found, print it directly
}
}
cout << endl; // new line after transposing
return 0;
}
Previous
|<Qualifications for district competitions
