Jan 28 - Daily Programming Diary

28.01.2021 — Diary, Programming — 2 min read

10:00

I was doing the Leetcode Challenge last night but decided to do it in the morning instead. Now with my brain working in a better condition, I think it's time to solve the problem.

Just get the number of bits in the current number, and multiply the answer till now with 2 ^ NO_OF_BITS and take MOD.

concatenation-of-consecutive-binary-numbers.cpp

1int MOD = 1000000007;
2int countBits(unsigned int number) {
3    return (int)log2(number) + 1;
4}
5
6int concatenatedBinary(int n) {
7    long long ans = 1;
8    for (int i = 2; i <= n; i++) {
9        int digits = countBits(i);
10        while (digits--) {
11            ans *= 2;
12            ans %= MOD;
13        }
14        ans += i;
15        ans %= MOD;
16    }
17
18    return ans;
19}

Time complexity O(n logn), space O(1).

Time for Dijkstra's Algorithm now. I hope I can implement it.

12:17

Finally! God it feels so good! I can't believe I effing did it.

So, the approach right? I am maintaining a vector efforts regarding the efforts (cost) to be put to go to a particular node. Then inserting into set based on distance to get the minimum distance node. The vector visited tells whether the particular node has already been visited so as not to be stuck inside an infinite loop.

So after getting the minimum distance node, check the neighbors and update their efforts if the current node is a better way to reach that node.

Then update min_dist which stores the maximum of the minimum distance that need to be traversed at that point of time.

Problems faced

I was updating visited as soon as I inserted anything into the set, instead it should've been done when erasing it from set.
Updating min_dist as soon as I track the neighbors but it checks the visited property and then messes up the whole set.
Returning too early - As soon as the target node was removed from the set, I returned without giving the chance to actually update the min_dist. This is the part which is still a bit cloudy but it's probably because I'm not visiting a node until I track it's neighbors. This is related to the 2^nd issue.

path-with-minimum-effort.cpp

1int minimumEffortPath(vector<vector<int>> &heights) {
2    int m = heights.size(), n = heights[0].size();
3    int dx[4] = {1, 0, 0, -1};
4    int dy[4] = {0, 1, -1, 0};
5
6    int min_dist = 0;
7
8    vector<vector<int>> efforts(m, vector<int>(n, INT_MAX)); // All distance INF initially
9    vector<vector<bool>> visited(m, vector<bool>(n, false)); // No nodes visited initially
10    set<pair<int, pair<int, int>>> s;                        // To get node with MIN effort
11
12    efforts[0][0] = 0; // SRC Node has distance 0
13
14    s.insert(make_pair(0, make_pair(0, 0)));
15
16    while (!s.empty())
17    {
18        auto p = *(s.begin());
19
20        int row = p.second.first;
21        int col = p.second.second;
22
23        s.erase(s.begin());
24        visited[row][col] = true; // Current Node has been visited
25
26        min_dist = max(min_dist, efforts[row][col]);
27
28        for (int i = 0; i < 4; i++) {
29            int new_row = row + dx[i];
30            int new_col = col + dy[i];
31
32            if (new_row < 0 || new_row >= m || new_col < 0 || new_col >= n) {
33                continue;
34            }
35
36            if (abs(heights.at(new_row).at(new_col) - heights[row][col]) < efforts.at(new_row).at(new_col) && !visited[new_row][new_col]) {
37                auto f = s.find(make_pair(efforts.at(new_row).at(new_col), make_pair(new_row, new_col)));
38                if (f != s.end()) {
39                    s.erase(f);
40                }
41
42                efforts.at(new_row).at(new_col) = abs(heights.at(new_row).at(new_col) - heights[row][col]);
43
44                s.insert(make_pair(efforts.at(new_row).at(new_col), make_pair(new_row, new_col)));
45            }
46        }
47
48        if (row == m - 1 && col == n - 1) return min_dist;
49    }
50    return 0;
51}

Time complexity O(n*m + n*mlogn*m) (Dijkstra's) and space complexity O(m*n) where m and n are the rows and columns respectively.

14:00

Starting today's Leetcode challenge. Pretty basic problem after the above one. :p

Get the number of z in the string after accounting for the minimum number of a's to be inserted. Then add those z's. After that, add the character with the remaining value. Then remaining a's !

1string getSmallestString(int n, int k) {
2    k -= n;
3    string a = "";
4    int no_of_z = k / 25, j = 0;
5    k %= 25;
6    for (; j < no_of_z; j++) {
7        a += "z";
8    }
9    if (a.length() != n) {
10        a += ('a' + k);
11    }
12    for (; j < n - 1; j++) {
13        a += "a";
14    }
15
16    for (int i = 0; i < n / 2; i++) {
17        swap(a[i], a[n - 1 - i]);
18    }
19
20    return a;
21}

22:00

Gave Crio.do test on HackerRank. It was really difficult considering the fact that it was supposed to be a "BASIC DSA TEST". But anyway, I don't think I'll get selected for the second round.

Have to go to Gurgaon tomorrow! Hoping for some good news there!

Ciao!

EOD Checklist

Leetcode January Challenge
This blog