0%

Problem

You are given three integers n, m, k. A good array arr of size n is defined as follows:

Each element in arr is in the inclusive range [1, m].
Exactly k indices i (where 1 <= i < n) satisfy the condition arr[i - 1] == arr[i].
Return the number of good arrays that can be formed.

Since the answer may be very large, return it modulo 109 + 7.

Examples

Example 1

1
2
Input :n = 3, m = 2, k = 1
Output: 4

Explain: In the array, it should choose element from [1,2]. And there should be 1(k) pair of adjacent elements has the same value. The length of the array is 3. They are
[1,1,2],[1,2,2],[2,2,1],[2,1,1]

Example 2

1
2
Input: n = 4, m = 2, k = 2
Output: 6

Explanation:

The good arrays are [1, 1, 1, 2], [1, 1, 2, 2], [1, 2, 2, 2], [2, 1, 1, 1], [2, 2, 1, 1] and [2, 2, 2, 1].
Hence, the answer is 6.

Intuition

Emmmmmm, personally, it is impossible to enumerate all the possible arrays and check that they are ‘good’ or not. That makes time complexity blow up.(Btw, what is its complexity?) The best way to solve it is gorgeous math. Nani? We are going to solve this question with some black magic!
In array of length n, there are n-1 paris with adjacent element. Among n-1 pairs, k pairs must consist equal adjacent element and remaining n-1-k pairs must consist different adjacent elements. We can treat these n−1−k differing adjacent as partitions or bars(the stick.. not drinking one), which divide the array into n−k contiguous segments(stars), where each segment contains identical values. Yes! That’s is a altered combinatorial number question which most of Chinese senior high school student can tackle. If you are at sea pls clickBars and Stars.

  1. Among the n-1 positions between array elements, we choose n−1−k to place the partitions. This can be done in $\binom{n-1}{n-1-k} =\binom{n-1}{k}$ ways.
  2. The first segment can take any of the m values.
  3. Every subsegment (there are n−k−1 such subsegment) must differ from the previous’s value, meaning each of them has m−1 possible choices. Hence we have $(m-1)^{n-k-1}$.
    Sweeeeet, now we got the number $(n-1) * m *((m-1)^{n-k-1})$

U R highly recommended to read Binary Exponentiation and module-inverse OR (there is a better Chinese version)乘法逆元 before coding. Looking back, I’m thankful I wrestled with discrete math.

COOOOOOOOOOOOOOOOOOOOOOOOOOding

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
const int MOD = 1e9 + 7;
const int MX = 1e5;

long long fact[MX];
long long inv_fact[MX];

class Solution {
long long qpow(long long x, int n) {
long long res = 1;
while (n) {
if (n & 1) {
res = res * x % MOD;
}
x = x * x % MOD;
n >>= 1;
}
return res;
}
long long comb(int n, int m) {
return fact[n] * inv_fact[m] % MOD * inv_fact[n - m] % MOD;
}
void init() {
if (fact[0]) {
return;
}
fact[0] = 1;
for (int i = 1; i < MX; i++) {
fact[i] = fact[i - 1] * i % MOD;
}

inv_fact[MX - 1] = qpow(fact[MX - 1], MOD - 2);
for (int i = MX - 1; i; i--) {
inv_fact[i - 1] = inv_fact[i] * i % MOD;
}
}

public:
int countGoodArrays(int n, int m, int k) {
init();
return comb(n - 1, k) * m % MOD * qpow(m - 1, n - k - 1) % MOD;
}
};

If you are a python guy…. you can also…

1
result = math.comb(n-1, k) * m * pow(m-1, n-k-1, MOD) % MOD

Now which is the best language in the world?

Problem

Give integers n and k, list all numbers from 1 n in directory order, then return $k^{th}$ number in that list.

Logic

Intuitively, we can generate all numbers $[1..n]$, convert to string, sort, resulting to an $O(O log n)$.
Brutely, we can have the following code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int findKthNumber(int n, int k) {
vector<string> nums;

for (int i = 1; i <= n; i++) {
nums.push_back(to_string(i));
}

sort(nums.begin(), nums.end());

return stoi(nums[k - 1]);
}
};

No surprise, Time Limit Exceeded.

The directory sequence corresponds to a 10-ary prefix tree of numbers. Each node x has children x0, x1,...,x9(of course if it still <=n ).

We can count how many nodes are in each subtree and skip entire subtree when their size < k.
we can have following solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int findKthNumber(int n, int k) {
int curr = 1;
k--;// 0-indexed

while(k > 0){
int steps = countSteps(n, curr, curr + 1);
if(steps <= k){
//skip this subtree, go to next sibling
curr++;
k -= steps;
}
else{
//answer is in this subtree let's go deeper
curr *= 10;
k--;
}
}
return curr;
}
};

countStep will calculate how many numbers exist with a prefix between ‘curr’ and ‘next’, and it should be <=n.

1
2
3
4
5
6
7
8
9
static long countSteps(long long curr, long long next, long n){
int steps = 0;
while (curr <= n) {
steps += min((long long)n + 1, next) - curr;
curr *= 10;
next *= 10;
}
return steps;
}

In Single Cycle processor, as its name, it should done one instruction in one clock cycle(which also means CPI=1). But it seems that the latencies varies from instruction to instruction. In order to guaranty every instruction finish, the clock cycle is determined by the longest instruction latency. Yes, that’s wasting lots of time.

Can we have a better solution? We can partition each sub-instruction or(sub-behavior). In this section, we should try to balance the time spend in each section.

For each partition, we need to determine some registers the datapath should be accessed. In other words, we need to store something from previous partition, and use them in current partition.

We can have an example on I-type operation. It can be done in 4 clock cycle.

  • IR <- IM[PC]
  • A <- R[rs]
  • s <- a op zero_ext(imm)
  • R[rt] <- S; PC <- PC+4


Comparing 2 picture above, we can observe multiCycle Processor has a much complexer control unit(FSM). And some registers are added to design, dividing a Processor to several part. The main reason of FMS has more signal output is the increased number of registers.

However, consider we have are doing an I-type operation. When we are doing A <- R[rs], the previous part(instruction registers) is unused. That’s a kind of resource waste. To solve it we can design a Pipeline processor.

Problem

Given a 0-indexed integer array nums of size n, find the maximum difference between nums[i] and nums[j] (i.e., nums[j] - nums[i]), such that 0 <= i < j < n and nums[i] < nums[j].

Return the maximum difference. If no such i and j exists, return -1.

Intuition

The brute solution is easy. We can have 2 pointers do iteration which would result in a time complexity of $O(n^2)$.

That’s so dumb… Can we have a better solution?

Consider how max difference come from? Now we have are in num[i]. The max diff show be updated to num[i]- min(num[0], num[i-1]) if prefix_res < res. Nice! we may keep the track of min value in previous data.

In each iteration, if num[i] < min(num[0], num[i-1]) then we update the minValue else we can update res = max(res, num[i] - minValue). Sweeeeeet! We optimize it to $O(n)$.

Cooooooooding

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int maximumDifference(vector<int>& nums) {
int res = -1;
int min = nums[0];
for(int i = 1; i < num.size(); i++){
if(nums[i] <= min){
min = nums[i]
}
else{
res = max(nums[i] - min, res);
}
}
return res;
}
};

Problem

You are given an integer num. Bob will sneakily remap one of the 10 possible digits(0 to 9) to another digit.

Return the difference between the maximum and minimum value Bob can make by remap exactly one digit in num.

Bob can remap a digit to it self.(not change)

Resulting number after remapping can not contain leading zeros.

Intuition

This problem is like to Leetcode2567, Yes…exactly the daily question in Leetcode yesterday. The only difference is that we canNOT have leading zeros today.
We need to consider how to get the minimum value. Is that replacing all first digit to 1? Apparently not, 11111 the min value should be 10000.

Can we do the same thing in the way of finding the max value? Replace the first non-1 digit to 0? No…. which breaks the rule no leading zero..

Then maybe if the first digit is not 1, we replace it to 1. And for non-first digit, we change it to 0.

COOOOOOOOOOOOODING

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution{
public:
int maxDIff(int num){
string s = to_string(num);
int index_max = -1;
int index_max = -1;

for(int i = 0; i <s.length(); i++){
if(s[i] != '9' && index_max == -1){
index_max = i;
}
if(index_min == -1){
if(i == 0 && s[i] != '1') {
index_min = i;
}
else if(i > 0 && s[i] != '0' && s[i] != s[0]) {
index_min = i;
}
}
}
string s_max = s;
if(index_max != -1) {
for(char& ch : s_max) {
if(ch == s[index_max]) ch = '9';
}
}

string s_min = s;
if(index_min != -1) {
char replacement = (index_min == 0) ? '1' : '0';
for(char& ch : s_min) {
if(ch == s[index_min]) ch = replacement;
}
}

int max_val = stoi(s_max);
int min_val = stoi(s_min);
return max_val - min_val;
}
}

Problem

You are given an integer num. Bob will sneakily remap one of the 10 possible digits(0 to 9) to another digit.

Return the difference between the maximum and minimum value Bob can make by remap exactly one digit in num.

Bob can remap a digit to it self.(not change)

Resulting number after remapping can contain leading zeros.

Intuition

Consider the number 11891, Bob can remap 1 to 9 to obtain the max 99899, and remap 1 to 0 to obtain the min 00890.

Consider the number 99919, Bob can remap 1 to 9 to obtain the max 99999, and remap 9 to 0 to obtain the min 00010.

Hence we can observe that remap the first non-9 digit to 9 to yield the max value. And replace the first digit to 0 to yield the min value.

COOOOOOOOOOOOODING

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution{
public:
int minMaxDifference(int num){
string s = to_string(num);
int i = 0;
while(s[i] == '9' && i < s.length()-1) i+=1;

string max = s;
for(char& ch:max) if(ch==s[i]) ch='9';

string min = s;
for(char& ch:min) if(ch==s[0]) ch='0';
return stoi(max)-stoi(mn);
}
}

Super classes, Object, and Class Hierarchy

  • Every class have a superclass
  • If we don’t define the superclass, by default, it will be the class Object

Object class

  • It is the only class that does not have a superclass

Often we need to override the following methods

  • toString()
  • equals()
  • hasCode()

Abstract classes

Using Abstract classes, we can declare classes that define ONLY part of implementation, leaving extended classes to provide specific implementation of some or all the methods

One good example will be

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public abstract class Shape {

public abstract double area();

public abstract double circumference();

protected static int count_shapes = 0;

public void printArea() {
System.out.println(" (from Shape abstract class, method printArea)> area is: " + this.area());
}

}

public class Rectangle extends Shape {
protected double width, height;

public Rectangle() {
width = 1.0;
height = 1.0;
count_shapes++;
}

public Rectangle(double w, double h) {
this.width = w;
this.height = h;
count_shapes++;
}

public double area() {
return width * height;
}

public double circumference() {
return 2 * (width + height);
}

}

We can also invokeshapes[].area(). Java will automatically use the implementation.

Interfaces in JAVA

All the methods defined within an interface are implicitly abstract, which means that the class/abstract class MUST have implementation for all of its method.

Approach: binary + greedy

Intuitively, we do a sort for this array.

Since we are looking to minimize the maximum difference, one brute force approach is to start from a threshold (a maximum difference) of ‘0’ and incrementally try all possible thresholds

  1. Try to find ‘p’ pairs with difference of ‘0’
  2. if not possible then we try to find ‘p’ pairs with difference of ‘1’
  3. and so on, until we find a threshold that succeeds.

As you may notice, this will cost a linear time for each threshold. Do we have a better solution?
We observe that

  • If we can find p pairs with threshold of x, then we can definitely find p pairs of with a threshold of x+1
  • If we can NOT find p pairs with threshold of x, we definitely can not find p pairs with threshold of x-1

This splits the number line into two sections: one section where the task is possible, and one where the task is impossible. Therefore, we can use binary search to quickly narrow down the search space until we find the dividing point, which is the minimum threshold.

Now we go to next question, how do we determine if there exist at least p valid pairs.

How about greedy? We do iteration to nums[]. check each abs(nums[i] - nums[i+1]) <= 'threshold, if is true then simply check num[i+2] and num[i+3].

But I will question myself. Does greedy solution will fail and another solution will succeeds?

  1. Suppose greedy fails but some better strategy succeeds
  2. Then at first difference, greedy pairs (nums[i], num[i+1]) but optimal way dosen’t
  3. In the potimal solution, num[i] either:
  • pairs with num[j] where j > i+1 then difference must greater or equal to nums[i+1] -nums[i] (worse!)
  • unpaired (worse, cuz we lost a pair)
    `
  1. We can always “exchange” the optimal pairing to use (nums[i], nums[i+1]) instead
  2. Same or better solution, contradicting that optimal was better

OK now The greedy approach will always yield the maximum number of valid pairs.

Let’s do COOOOOOOOOOOOODING

  1. Define countValidPairs(threshold) to find the number of pairs having a threshold of threshold in nums. Let n be the size of nums.
  • set count = 0
  • Iterate over nums from index = 0to index = n - 2. If nums[index + 1] - nums[index] <= threshold, increment count by 1, and skip both indices. Otherwise, skip the current index.
  • Return count
  1. sort nums
  2. Initialize the searching space as left = 0 and right = nums[n -1] - nums[0], the max difference in the array.
  3. while left < right , we do
  4. Get the middle value as mid = left + (right - left)/2
  5. invoke countValidPairs(mid)
  6. if countValidPairs(mid), continue with the left half by setting(right = mid). Otherwise, continue with the right half by setting left = mid -1Repeat step 4
  7. Return left
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    class Solution {
    public:
    // Find the number of valid pairs by greedy approach
    int countValidPairs(vector<int>& nums, int threshold) {
    int index = 0, count = 0;
    while (index < nums.size() - 1) {
    // If a valid pair is found, skip both numbers.
    if (nums[index + 1] - nums[index] <= threshold) {
    count++;
    index++;
    }
    index++;
    }
    return count;
    }

    int minimizeMax(vector<int>& nums, int p) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    int left = 0, right = nums[n - 1] - nums[0];

    while (left < right) {
    int mid = left + (right - left) / 2;

    // If there are enough pairs, look for a smaller threshold.
    // Otherwise, look for a larger threshold.
    if (countValidPairs(nums, mid) >= p) {
    right = mid;
    } else {
    left = mid + 1;
    }
    }
    return left;
    }
    };

Question:Given a circular array nums, find the maximum absolute difference between adjacent elements.

Note: In a circular array, the first and last elements are adjacent.

Easy question directly answer

1
2
3
4
5
6
7
8
9
10
11
class Solution{
public:
int maxAdjacentDistance(Vector<int>& nums){
int n = num.size();
int res = abs(nums[0] - nums[n-1]);
for(int i = 0; i <n-1; i++){
res = max(res, abs(nums[i] - nums[i+1]));
}
return res;
}
}

In this lab we are required to build a hardware model for accumulation of a sequence of Bfloat16 values and implement it on the lab board.Here we assume all values are positive and no overflow will occur. Each input
Value is set by the switches and the accumulative result for each new input is displayed on the LED array.

Since we have a bottom to make operation compute, we may need a FSM. Intuitively, we will only need 2 state “idle & compute”.

Accumulator

In order to make accumulation for 2 Bfloat16 number we have the following number.
We have the following steps.

  1. Extract Component
    Extract the current number to 2 field: Exponent & Fraction.(Since no need for sign bits since all positive)

    1
    2
    exp_a <= a(14 downto 7);
    frac_a <= a(6 downto 0);

    If Exponent part is 0, then this number is 0;

    1
    a_is_Zero <= '1' when unsigned(exp_a) = 0 else '0';

  2.  Align Frac Field
    
  3. third