Rectangle
Problem Statement
You are given a list of nondecreasing numbers. Your task is to find the minimum differences between any two numbers.
Input Format
You will be given a list of numbers numbers
.
Output Format
Output the minimum differences between any two numbers.
Sample
Input
numbers = [1, 5, 7, 10, 12]
Output
2
Explanation
The difference between the number 5 and 7 is minimum (or 10 and 12).
We find the xcoordinate and ycoordinate of the fourth point separately. Observe that for any rectangle with sides parallel to the x and y axes, the corners can be split into two pairs, each pair with the same xcoordinate. We have the xcoordinates of three points, with two of them being the same. The fourth point’s xcoordinate is the xcoordinate which is different. We can find the ycoordinate analogously.
Solution
The naive solution is that we compute the difference between every pair of elements. However, since the array is already sorted in nondecreasing order, we can observe that for each number, the smallest difference must be the difference between the current number and the adjacent number in the array. Thus, we can solve this question by looping through the array and compute the difference between each pair of adjacent element while maintaining the minimum difference.
The complexity of the solution is O(N).
Python 3
numbers = [1, 5, 7, 10, 12]
minimum = numbers[1]numbers[0]
for i in range(1,len(numbers)):
minimum = min(minimum,numbers[i]numbers[i1])
print(minimum)
C++
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector <int> numbers = {1, 5, 7, 10, 12};
int minimum = numbers[1]numbers[0];
for (int i=1;i<numbers.size();i++){
minimum = min(minimum,numbers[i]numbers[i1]);
}
cout << minimum << endl;
}
Bakery
MCC bakery has a promotion:
When you buy 4 pieces of bread, the second cheapest one is free of charge!
You want to buy n pieces of bread (where n is a multiple of 4) and are given the price of each bread you want to buy. What is the minimum amount you have to pay to purchase all the bread?
Input Format
You will be given a list of numbers prices
indicating the price of each bread you want to buy. It is guaranteed that the length of prices
is a multiple of 4.
Output Format
The minimum amount you have to pay to purchase all the bread.
Sample
Input
prices = [3, 2, 6, 8, 10, 1, 7, 9]
Output
35
Explanation
You can buy in 2 batches (2, 8, 10, 9) to get the one that costs 8 free and (3, 6, 1, 7) to get the one that costs 3 free. In the end you only have to pay 2+10+9+6+1+7=35.
Solution
The best strategy to buy the bread is that we group 3 most expensive bread with the cheapest bread. So first we sort the prices of the bread in ascending order then we can solve this question by using a deque.
The complexity of the solution is O(NlogN).
Python 3
import collections
prices = [3, 2, 6, 8, 10, 1, 7, 9]
prices.sort()
prices = collections.deque(prices)
pay = 0
while(len(prices) > 0):
pay += prices.pop()
pay += prices.pop()
prices.pop() # we can get the third expensive bread for free
pay += prices.popleft()
print(pay)
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
deque <int> prices = {3, 2, 6, 8, 10, 1, 7, 9};
sort(prices.begin(),prices.end());
int pay = 0;
while (prices.size() > 0){
pay += prices[prices.size()1];
pay += prices[prices.size()2];
pay += prices[0];
prices.pop_back();
prices.pop_back();
prices.pop_back();
prices.pop_front();
}
cout << pay << endl;
}
Candy
Problem Statement
Cindy is a very generous teacher and decides to give out a piece of candy to one of her infinite number of students! She has created a game to help her select which student to give the candy to.
The game consists of N rounds. The game goes as follow:

All of her students are queuing in a line. Then they start the first round.

Cindy will either shout
"odd"
or"even"
. 
If she shouted
"odd"
, all the students currently standing at oddnumbered positions are eliminated from the game. Similarly, if she shouted"even"
all the students currently standing at evennumbered positions are eliminated from the game. Students who are eliminated will no longer be in the queue. 
The remaining surviving students will play again without switching places from step 2 for another round, or stop playing if N rounds have been played.
After N rounds, Cindy will give the candy to the first student in the queue.
Bob knows what Cindy will shout at each round and really wants the candy. He wonders where should he stand in the queue initially (round 1) so that he can get the candy. Can you help Bob?
Input Format
You will be given a list shouts
, with N strings of either "even"
or "odd"
. The ith item in the list is what Cindy will shout on the ith round.
Output Format
Output the number of the position Bob should stand at the start of the game.
Sample
Input
shouts = ["even", "even", "odd"]
Output
5
Explanation
We can illustrate the process of the game. Let’s label each student by the number of their initial position, and Bob’s number, 5
in this case, is marked with an asterisk (*).
Initial queue:
1, 2, 3, 4, 5*, 6, 7, ...
Queue after round 1 ("even" shouted):
1, 3, 5*, 7, 9, 11, 13, ...
Queue after round 2 ("even" shouted):
1, 5*, 9, 13, 17, 21, ...
Queue after round 3 ("odd" shouted):
5*, 13, 21, ...
Bob is the first student after the game, and he was awarded the candy!
Solution
First we represent every position as binary digits.
0 => 0
1 => 1
2 => 10
3 => 11
4 => 100
5 => 101
6 => 110
...
If Cindy first shouted “even” then means that all students standing in an even position will be eliminated i.e students with index (1, 3, 5, 7 …) will be eliminated. So the last bit of Bob’s position must be 0. For the same reason, if Cindy shouted “odd” then students with index (0, 2, 4, 6 …) will be eliminated thus the last bit of Bob’s position must be 1.
Then we can observe that for the ith shout, if “even” is shouted then ith last bit must be 0 . If “odd” is shouted then ith last bit must be 1 .
But since indices and positions differ by one, we must add 1 to our answer to tell the position instead of index
Thus we can do simple implementation on this and the complexity of the solution is O(N).
Python 3
shouts = ["even", "even", "odd"]
n = 1
for i in range(len(shouts)):
if (shouts[i] == "odd"):
n += 2**i
print(n)
C++
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector <string> shouts = {"even", "even", "odd"};
long long n = 1;
for (int i=0;i<shouts.size();i++){
if (shouts[i] == "odd"){
n += (long long)(1) << i;
}
}
cout << n << endl;
}
Ditcoin
Problem Statement
You earn one Ditcoin every day. You also know the future price of the ditcoin. A ditcoin earned on that day can be sold on that day or in the future days. You can sell any amount of ditcoin on a given day. Your task is to compute the maximum amount of money you can earn by selling your ditcoins optimally.
Input Format
You are given a list of prices prices
indicating the amount you can earn if you sell a ditcoin on that day.
Output Format
The maximum amount of money you can earn.
Sample
Input
prices = [3, 2, 6, 8, 10, 1, 7, 9]
Output
77
Explanation
If you sell your 1st to 5th ditcoin of the 5th day, you earn 5\times 10=50, and the rest on the last day to earn 3\times 9 = 27 more. In total, you will earn 77.
Solution
To get the maximum amount of money, we should look for the day which has the highest Ditcoin selling price, and then sell all the Ditcoins we have accumulated before that day.
Let’s call this special day a S day.
But if the day of the highest price is not the last day, then we have to find another day with the highest price from S day to the last day.
Naive solution is to do a left to right loop repeatedly from S day to the last day to find the day with maximum price. The complexity of this solution is O(N^2).
We can optimize the naive solution by looping from behind. Recording the highest price from the current element to the last element. Then the profit of the coin earn on that day will be the current maximum. The complexity of this solution is O(N).
Python 3
prices = [3, 2, 6, 8, 10, 1, 7, 9]
maximum = 0
ans = 0
for i in reversed(prices):
maximum = max(maximum,i)
ans += maximum
print(ans)
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
vector <int> prices = {3, 2, 6, 8, 10, 1, 7, 9};
int maximum = 0;
int ans = 0;
for (int i=prices.size()1; i>=0; i){
maximum = max(maximum,prices[i]);
ans += maximum;
}
cout << ans << endl;
}
Elimination
Problem Statement
A binary string is a string where each character is either 0
or 1
.
Given a binary string and a number k, find the length of the longest consecutive 1’s after removing at most k 0’s from the binary string.
Input Format
You will be given a binary string string
and a number k
.
Output Format
Output the length of the longest consecutive 1’s after removing at most k
0’s.
Sample
Input
string = "101111001110111"
k = 1
Output
6
Explanation
We can remove the 0 between the 2 "111"
substring to get "111111"
as a substring. This is clearly the longest consecutive 1’s we can get.
Solution
Solution
We can use two pointer technique to solve this problem.
Let r be the end of a segment of the binary string.
Let l be the start of a segment of the binary string.
We find the largest r for every l.
Complexity of this solution is O(N).
Python 3
string = "101111001110111"
k = 1
left = 0 #left and right means [left,right] segment
zero = 0
one = 0
#zero and one means how many zero and one are there currently
ans = 0
#the idea is for each right, what's the smallest left you can get?
#this technique is called two pointers
for right in range(len(string)):
if (string[right] == "0"): #if the element in the current right is zero
zero += 1
while (zero > k):
# means you have eliminated more than k zero
# so you must increase your left to eliminate some zero
if (string[left] == "0"): zero = 1
else: one = 1
left += 1
else:
one += 1
ans = max(ans,one)
print(ans)
C++
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){
string s = "101111001110111";
int k = 1;
int left = 0,right = 0; // left and right means [left,right] segment
int n = s.size();
int zero = 0,one = 0; // zero and one means how many zero and one are there currently
int ans = 0;
// the idea is for each right, what's the smallest left you can get?
// this technique is call two pointers
for (int right = 0; right < n; right++){
if (s[right] == '0'){ // if element in the current right is zero
zero++;
while (zero > k){
// means you have eliminated more than k zero
// so you increase your left to eliminate some zero
if (s[left] == '0') zero;
else one;
left++;
}
} else {
one++;
ans = max(ans,one);
}
}
cout << ans << endl;
}
Palindrome
Problem Statement
A palindrome is a string that is identical when read from left to right and from right to left. For example, "racecar"
and "0110"
are palindromes.
A string is called a kpalindrome if it is a palindrome and also each character is either 0, 1, … or k1 for some 2 \leq k \leq 10. For example. "302203"
is a 4palindrome, 5palindrome, 6palindrome and so on, but it is not a 2palindrome and also not a 3palindrome.
Bob came across a book titled k for some 2 \leq k \leq 10. It has an infinite margin and consists of all possible kpalindromes. The book arranges the palindromes in a list in the following fashion:
 If two strings are different in length, the shorter one goes first
 If they are the same in length, the lexicographically smaller string goes first, like in dictionaries.
For example, the first 10 words in book 2 will be:
0
1
00
11
000
010
101
111
0000
0110
Bob wonders what is nth string in the book. Can you help him out?
Input Format
You will be given two numbers, n
and k
, the position (1index) of the word Bob is interested in and the title of the book.
Output Format
Output the nth string in the book.
Sample
Input
7 3
Output
000
Explanation
The first 7 words of the book 3
are as follow:
0
1
2
00
11
22
000
So the 7th word is "000"
.
Solution
First we must compute the length of the answer. Let’s make a table visualizing how many valid palindromes are there for each length.
Take k = 3
length  palindromes  number of valid palindrome 

1  0 1 2  3 
2  00 11 22  3 
3  000 010 020 101 111 121 202 212 222  9 
4  0000 0110 0220 1001 1111 1221 2002 2112 2222  9 
As shown in the table, the right half of the palindrome will decide the left half of the palindrome. In addition, for each number in the right half we can modify it by k times. Hence, we prove that for l length palindrome there will be k^{\lceil(l/2\rceil} valid palindromes. We can conclude this observation by the following formula.
k^{\lceil(1/2\rceil}+ k^{\lceil(2/2\rceil} + k^{\lceil(3/2\rceil} + k^{\lceil(4/2\rceil} + k^{\lceil(5/2\rceil} + k^{\lceil(6/2\rceil} + … + k^{\lceil(c/2\rceil} \ge n ,c \in \mathbb{N}
So by using formula, we can then find the smallest c that satisfies the inequality and the smallest c would be the length of the answer.
Now we let a be the length of the answer.
Taking k = 4
Taking l = 4
0000 => 0th palindrome , 0 in base 4 = 0
0110 => 1st palindrome , 1 in base 4 = 1
0220 => 2nd palindrome , 2 in base 4 = 2
0330 => 3rd palindrome , 3 in base 4 = 3
1001 => 4th palindrome , 4 in base 4 = 10
1111 => 5th palindrome , 5 in base 4 = 11
...
Observe that lexicographically sorted kpalindrome has a relation with base k. We just need to find the order of the answer in a length then we can compute the answer.
let the order of the answer in a length be r
r = n  (k^{\lceil(1/2\rceil}+ k^{\lceil(2/2\rceil} + k^{\lceil(3/2\rceil} + k^{\lceil(4/2\rceil} + k^{\lceil(5/2\rceil} + k^{\lceil(6/2\rceil} + … + k^{\lceil((a1)/2\rceil})  1
The reason to 1 is because the order starts from 0th.
We change r to base k and that will provide us the answer.
import math
n = 18
k = 3
s = 0
c = 0
r = n
while (s < n):
c += 1
s += k**math.ceil(c/2)
for i in range(1,c):
r = k**math.ceil(i/2)
r = 1
#c is the length, r is the order
# change base
ans = ""
while (r > 0):
ans += str(r%k)
r = r//k
while (len(ans)*2 < c):
ans += '0'
if (len(ans)*2 == c):
print(ans[::1]+ans)
else :
print(ans[:0:1]+ans)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
ll power(ll x, ll y) // function to compute power
{
ll ans = 1;
while (y > 0)
{
if (y & 1) ans = (ans*x);
y = y>>ll(1);
x = (x*x);
}
return ans;
}
int main(){
ll n = 7,k = 3;
ll sum = 0;
ll c = 0;
ll r = n;
while (sum < n){
c++;
sum += power(k,ceil(ld(c)/ld(2)));
}
for (int i=1;i<c;i++){
r = power(k,ceil(ld(i)/ld(2)));
}
r;
// c is the length , r is the order
// change base
string ans = "";
while (r > 0){
ans += to_string(r%k);
r /= k;
}
while(ans.size()*2 < c){
ans += '0';
}
string rans = ans;
reverse(ans.begin(),ans.end());
if (ans.size()*2 == c){
cout << ans << rans << endl;
} else {
for (int i=0;i<ans.size()1;i++){
cout << ans[i];
}
cout << rans << endl;
}
}