Alternating Characters

Solutions This problem can be solved by counting the number of equal adjacent characters: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 size_t T; cin >> T; string s; while (T--) { cin >> s; auto cnt = 0; for (auto i=1; i<s.size(); ++i) { if (s[i]==s[i-1]) cnt++; } cout << cnt << "\n"; } This is an application of zip | map | reduce pattern: [Read More]

Arron Maximum Profit

Solutions This problem is an application of Find the Maximum Difference. Basically, we need to find out the maximum difference between two numbers in the given array \(max(prices[j] - prices[i])\) with \(i<j\). The bruce force approach is quadratic and does not pass all test cases: for each element we linearly find the biggest next value. As discussed in Find the Maximum Difference, the general solution schema is the following: 1 2 3 4 5 6 7 8 9 auto currMin = INT_MAX; auto currMax = 0; for (auto i : prices) { currMin = min(currMin, i); currMax = max(i - currMin, currMax); } cout << currMax; As long as we iterate the array, currMin keeps track of the smallest element along the way. [Read More]

Birthday Chocolate

Solutions The solution to this problem when d=1 can be used to solve Picking Numbers as well. A linear solution consists in: computing the prefix sum of the input array keeping a window of size m counting how many times the window bounds differ by d Here is a solution in C++: 1 2 3 4 5 6 7 8 9 10 11 12 13 int n, d, m; cin >> n; vector<int> v(n+1); copy_n(istream_iterator<int>(cin), n, next(begin(v))); cin >> d >> m; partial_sum(begin(v), end(v), begin(v)); auto cnt = 0; for (auto i=0; i<=n-m; ++i) { cnt += v[i+m] - v[i] == d; } cout << cnt; The loop can be replaced with zip | map | reduce combination of patterns: [Read More]

CamelCase

Solutions The problem is very simple: we just count how many capital letters the string has and we sum 1. A C++ Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 #include <string>#include <iostream>#include <algorithm>#include <iterator> using namespace std; int main() { cout << (count_if(istream_iterator<char>(cin), istream_iterator<char>(), [](char c){ return isupper(c); })+1); } Here is a Python solution by Yuri Valentini: 1 2 ss = raw_input(). [Read More]

Compare the Triplets

Solutions This is clearly an easy problem we can experiment with. The easiest way to write the solution in C++ is: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 array<int, 3> a, b; copy_n(istream_iterator<int>(cin), 3, begin(a)); copy_n(istream_iterator<int>(cin), 3, begin(b)); int alice_points = 0; int bob_points = 0; for(int i = 0; i < 3; i++) { if (a[i] > b[i]) alice_points++; if (a[i] < b[i]) bob_points++; } A little more efficient: else if [Read More]

Counting Valleys

Solutions Intuition: we keep track of how many steps we are on or under the sea (e.g. variable level). When we go down (e.g. we read D) we decrement our level by one. When we go up we increment our level by one and also check if we were just one level below the sea. If the case, we are walking through a valley (e.g. we increment a counter). C++ Here is a C++ implementation of the idea above: [Read More]

Find the Maximum Difference

You are given a sequence of integers S, your task is to find a pair i,j of indices with i<j that maximizes the difference S[j]-S[i]. Note that what makes this challenge more interesting is the requirement of order, that i < j (without it you simply need to find the maximum and minimum element of S). You have to output the value of the maximum difference. Input Format An integer N followed by N space separated integers S[i] on a new line. [Read More]

Gap Up and Down

John has been analyzing stocks and their prices as his latest assignment. Being a beginner in stocks, he has selected a stock HRC and collected the low, high and close prices for n days in the form of arrays: \(low\), where \(low_i\) is the lowest value of the stock on \(i^{th}\) day. \(high\), where \(high_i\) is the highest value of the stock on \(i^{th}\) day. \(close\), where \(\) is the closing value of the stock on \(i^{th}\) day. [Read More]

Jim and the Orders

Solutions This is a simple greedy algorithm. Naming \(t_i\) the time of order \(i\) and \(d_i\) the time needed to complete order \(i\), we sort all the orders by \(t_i + d_i\) and by \(i\). The idea implemented in C++: 1 2 3 4 5 6 7 8 9 10 int N, ti, di; cin >> N; vector<pair<int, int>> orders(N); for (auto i=1; i<=N; ++i) { cin >> ti >> di; orders[i-1] = {ti+di, i}; } sort(begin(orders), end(orders)); for (const auto& o : orders) cout << o. [Read More]

Left Rotation

Solutions A tradeoff of this problem is about using a temporary array or not. In the latter case, the steps to do are simpler because we can just copy the two parts the array: all the elements before the rotation point and then all the element after. Here is a Java implementation: 1 2 3 4 5 6 7 8 9 10 11 public static int[] rotateArray(int[] arr, int d) { int n = arr. [Read More]