Rectangle

Problem Statement

You are given a list of non-decreasing 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 x-coordinate and y-coordinate 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 x-coordinate. We have the x-coordinates of three points, with two of them being the same. The fourth point’s x-coordinate is the x-coordinate which is different. We can find the y-coordinate analogously.

Solution

The naive solution is that we compute the difference between every pair of elements. However, since the array is already sorted in non-decreasing 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[i-1])

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[i-1]);
    }

    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:

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

2. Cindy will either shout "odd" or "even".

3. If she shouted "odd", all the students currently standing at odd-numbered positions are eliminated from the game. Similarly, if she shouted "even" all the students currently standing at even-numbered positions are eliminated from the game. Students who are eliminated will no longer be in the queue.

4. 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 i-th item in the list is what Cindy will shout on the i-th 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 i-th shout, if “even” is shouted then i-th last bit must be 0 . If “odd” is shouted then i-th 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 k-palindrome if it is a palindrome and also each character is either 0, 1, … or k-1 for some 2 \leq k \leq 10. For example. "302203" is a 4-palindrome, 5-palindrome, 6-palindrome and so on, but it is not a 2-palindrome and also not a 3-palindrome.

Bob came across a book titled k for some 2 \leq k \leq 10. It has an infinite margin and consists of all possible k-palindromes. The book arranges the palindromes in a list in the following fashion:

1. If two strings are different in length, the shorter one goes first
2. 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 n-th string in the book. Can you help him out?

Input Format

You will be given two numbers, n and k, the position (1-index) of the word Bob is interested in and the title of the book.

Output Format

Output the n-th 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 7-th 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

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 k-palindrome 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((a-1)/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;
	}
}