2020-06-14

HackerRank - Regex - Assertions

Positive Lookahead

regex_1(?=regex_2)

The positive lookahead (?=) asserts regex_1 to be immediately followed by regex_2. The lookahead is excluded from the match. It does not return matches of regex_2. The lookahead only asserts whether a match is possible or not.

For Example

c(?=o)

is matched with chocolate

Task

gooooo!

o(?=oo)

Negative Lookahead

regex_1(?!regex_2)

The negative lookahead (?!) asserts regex_1 not to be immediately followed by regex_2. Lookahead is excluded from the match (do not consume matches of regex_2), but only assert whether a match is possible or not.

For Example

c(?!o)

is matched with chocolate

Task

If S =goooo, then regex should match goooo. Because the first g is not follwed by g and the last o is not followed by o.

gooooo

1	(\S)(?!\1)

Positive Lookbehind

(?<=regex_2)regex_1

The positive lookbehind (?<=) asserts regex_1 to be immediately preceded by regex_2. Lookbehind is excluded from the match (do not consume matches of regex_2), but only assert whether a match is possible or not.

For Example

1	(?<=[a-z])[aeiou]

is matched with helo

Task

123Go!

1	(?<=[13579])\d

Negative Lookbehind

(?<!regex_2)regex_1

The negative lookbehind (?<!) asserts regex_1 not to be immediately preceded by regex_2. Lookbehind is excluded from the match (do not consume matches of regex_2), but only assert whether a match is possible or not.

For Example

1	(?<![a-z])[aeiou]

is matched with helo

Task

1o1s

1	(?<![aeiuoAEIOU]).

Resources

Regex - Subdomains - Assertions

2020-06-09

LeetCode - Algorithms - 793. Preimage Size of Factorial Zeroes Function

Problem

793. Preimage Size of Factorial Zeroes Function

Relevant problem

An easy problem as 172. Factorial Trailing Zeroes and its solutions: https://hezhigang.github.io/2020/06/06/LeetCode-Algorithms-factorial-trailing-zeroes/

Java

Binary Search strategy

Binary search, also known as half-interval search, logarithmic search, or binary chop, is a general algorithm for linearly ordered data structure, and There are numerous variations of binary search.

Let $ f(x) $ be the number of zeroes at the end of $x!$. We can observe that $ f(x) $ rise when $ x \equiv 0 \hspace{2mm} (mod \hspace{1mm} 5) $,
and $ f(5k)=f(5k+1)=f(5k+2)=f(5k+3)=f(5k+4) $.
$ f(x)=\lfloor \frac{x}{5} \rfloor + \lfloor \frac{x}{25} \rfloor + \cdots + \lfloor \frac{x}{5^n} \rfloor $ where $ \lfloor \frac{x}{5^n} \rfloor \geq 1 $
This geometric sequence with common ratio $ r = \frac{1}{5} $ has a limit that can be computed from the finite sum formula $ \sum_{k=1}^{\infty} \frac{x}{5^k} = \lim_{n \to \infty}\sum_{k=1}^{n} \frac{x}{5^k} = \frac{\frac{x}{5}}{1-\frac{1}{5}} = \frac{x}{4} $, so, there is a inequality that $ \frac{x}{5} < f(x) < \frac{x}{4} $, which gives a small upper and lower bound for binary search algorithm.

class Solution {
    public int preimageSizeFZF(int K) {
        int count = 0;
        long r = search_rank(K);
        count = r==-1?0:5;
        return count;
    }
    
    private long search_rank(long K) {
        long lo = 4*K;
        long hi = 5*K;
        while (lo <= hi) {
            long mid = lo + (hi - lo) / 2;
            long y = f(mid);
            if (K < y)
                hi = mid - 1;
            else if (K > y)
                lo = mid + 1;
            else
                return mid;
        }
        return -1;
    }

    private long f(long x) {
        long count = 0;
        for (long i = 5; i <= x; i *= 5)
            count += x / i;
        return count;
    }
}

Submission Detail

44 / 44 test cases passed.
Runtime: 0 ms, faster than 100.00% of Java online submissions for Preimage Size of Factorial Zeroes Function.
Memory Usage: 35.6 MB, less than 100.00% of Java online submissions for Preimage Size of Factorial Zeroes Function.

Complexity Analysis

Time Complexity

$ O(NlogN) $ where N is the input integer such that $ f(x)=N $

Space Complexity

$ O(1) $ as there is no extra space other than local varibles.

2020-06-07

HackerRank - Regex - Backreferences

Matching Same Text Again & Again

\group_number

This tool (\1 references the first capturing group) matches the same text as previously matched by the capturing group.

For Example

(\d)\1

It can match 00, 11, 22, 33, 44, 55, 66, 77, 88 or 99.

Task

ab #1?AZa$ab #1?AZa$

1	^([a-z])(\w)(\s)(\W)(\d)(\D)([A-Z])([a-zA-Z])([aeiouAEIOU])(\S)\1\2\3\4\5\6\7\8\9\10$

Backreferences To Failed Groups

Backreference to a capturing group that match nothing is different from backreference to a capturing group that did not participate in the match at all.

Capturing group that match nothing

(b?)o\1

is matched with o

Here, b? is optional and matches nothing.
Thus, (b?) is successfully matched and capture nothing.
o is matched with o and \1 successfully matches the nothing captured by the group.

Capturing group that didn’t participate in the match at all

(b)?o\1

is not matching o

In most regex flavors (excluding JavaScript), (b)?o\1 fails to match o.

Here, (b) fails to match at all. Since, the whole group is optional the regex engine does proceed to match o.
The regex engine now arrives at \1 which references a group that did not participate in the match attempt at all.
Thus, the backreference fails to match at all.

Task

12-34-56-78

12345678

1

1	^\d{2}(-?)\d{2}\1\d{2}\1\d{2}$

2

1	^\d{2}(-?)(\d{2}\1){2}\d{2}$

Branch Reset Groups

NOTE - Branch reset group is supported by Perl, PHP, Delphi and R.

(?|regex)

A branch reset group consists of alternations and capturing groups. (?|(regex1)|(regex2))
Alternatives in branch reset group share same capturing group.

1	(?\|(Haa)\|(Hee)\|(bye)\|(k))\1

is mathched with HaaHaa and kk

Task

12-34-56-78

12:34:56:78

12---34---56---78

12.34.56.78

1	/^\d{2}(?\|(-)\|(:)\|(---)\|(\.)\|){1}(\d{2}\1){2}\d{2}$/

Forward References

NOTE - Forward reference is supported by JGsoft, .NET, Java, Perl, PCRE, PHP, Delphi and Ruby regex flavors.

Forward reference creates a back reference to a regex that would appear later.
Forward references are only useful if they’re inside a repeated group.
Then there may arise a case in which the regex engine evaluates the backreference after the group has been matched already.

1	(\2amigo\|(go!))+

is matched with go!go!amigo

Task

tactactic

tactactictactic

1	^(\2tic\|(tac))+$

Resources

Regex - Subdomains - Backreferences

2020-06-06

LeetCode - Algorithms - 172. Factorial Trailing Zeroes

Problem

172. Factorial Trailing Zeroes

Java

solution of geeksforgeeks © Count trailing zeroes in factorial of a number

class Solution {
    public int trailingZeroes(int n) {
        int count = 0;
        for (long i = 5; i <= n; i *= 5)
            count += n / i;
        return count;
    }
}

Submission Detail

502 / 502 test cases passed.
Runtime: 0 ms, faster than 100.00% of Java online submissions for Factorial Trailing Zeroes.
Memory Usage: 36.6 MB, less than 31.99% of Java online submissions for Factorial Trailing Zeroes.

my solution

Accepted until 4th submission.

class Solution {
    public int trailingZeroes(int n) {
        if (n == 0)
            return 0;
        Double d = Math.floor((Math.log(n)) / (Math.log(5)));
        int m = d.intValue();
        int x = 0;
        for (int i = 1; i <= m; i++) {
            x += n / Math.pow(5, i);
        }
        return x;
    }
}

Submission Detail

502 / 502 test cases passed.
Runtime: 1 ms, faster than 20.14% of Java online submissions for Factorial Trailing Zeroes.
Memory Usage: 36.6 MB, less than 39.00% of Java online submissions for Factorial Trailing Zeroes.

my solution - 2

a one line function logarithm(n, r) which returns $ \lfloor \log_r n \rfloor $. © Program to compute Log n

class Solution {
    public int trailingZeroes(int n) {
        if (n < 5)
            return 0;
        int m = logarithm(n,5);
        int x = 0;
        for (int i = 1; i <= m; i++) {
            x += n / Math.pow(5, i);
        }
        return x;
    }
    
    private int logarithm(int n, int r) {
        return (n > r - 1) ? 1 + logarithm(n / r, r) : 0;
    }
}

Submission Detail

502 / 502 test cases passed.
Runtime: 1 ms, faster than 19.86% of Java online submissions for Factorial Trailing Zeroes.
Memory Usage: 38.6 MB, less than 5.16% of Java online submissions for Factorial Trailing Zeroes.

my solution - 3

class Solution {
    public int trailingZeroes(int n) {
        if (n < 5)
            return 0;
        long x = 0;
        long p = 5;
        while (n >= p) {
            x += n / p;
            p *= 5;
        }
        Long l = new Long(x);
        return l.intValue();
    }
}

Submission Detail

502 / 502 test cases passed.
Runtime: 1 ms, faster than 19.86% of Java online submissions for Factorial Trailing Zeroes.
Memory Usage: 36 MB, less than 94.80% of Java online submissions for Factorial Trailing Zeroes.

my solution - 4

class Solution {
    public int trailingZeroes(int n) {
        if (n < 5)
            return 0;
        int x = 0;
        for (long p = 5; n >= p; ) {
            x += n / p;
            p *= 5;
        }
        return x;
    }
}

Submission Detail

502 / 502 test cases passed.
Runtime: 2 ms, faster than 19.86% of Java online submissions for Factorial Trailing Zeroes.
Memory Usage: 38.1 MB, less than 10.66% of Java online submissions for Factorial Trailing Zeroes.

2020-06-05

LeetCode - Algorithms - 169. Majority Element

There are many solutions to an easy problem.

Problem

169. Majority Element

Java

sorting

import java.util.*;

class Solution {
    public int majorityElement(int[] nums) {
        final int len = nums.length;
        Arrays.sort(nums);
        return nums[len >> 1];
    }
}

Submission Detail

46 / 46 test cases passed.
Runtime: 1 ms, faster than 99.67% of Java online submissions for Majority Element.
Memory Usage: 42.9 MB, less than 72.59% of Java online submissions for Majority Element.

brute force

class Solution {
    public int majorityElement(int[] nums) {
        int half = nums.length >> 1;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i : nums) {
            Integer k = new Integer(i);
            if (map.containsKey(k)) {
                map.put(k, map.get(k)+1);
            }
            else {
                map.put(k, 1);
            }
        }
        int major = nums[0];
        for(Map.Entry<Integer, Integer> e : map.entrySet()) {
            if (e.getValue()>half) {
                major = e.getKey();
                break;
            }
        }
        return major;        
    }
}

Submission Detail

46 / 46 test cases passed.
Your runtime beats 37.72 % of java submissions.
Your memory usage beats 14.52 % of java submissions.

Boyer-Moore Voting Algorithm

class Solution {
    public int majorityElement(int[] nums) {
        int count=0;
        int candidate = nums[0];
        for(int num : nums) {
            if (count==0)
                candidate = num;
            count += (num == candidate) ? 1 : -1;
        }
        return candidate;        
    }
}

Submission Detail

46 / 46 test cases passed.
Runtime: 1 ms, faster than 99.67% of Java online submissions for Majority Element.
Memory Usage: 42.2 MB, less than 99.93% of Java online submissions for Majority Element.

2020-06-01

The Rainbow

by Christina Rossetti

Boats sail on the rivers,
And ships sail on the seas;
But clouds that sail across the sky
Are prettier than these.

There are bridges on the rivers,
As pretty as you please;
But the bow that bridges heaven,
And overtops the trees,
And builds a road from earth to sky,
Is prettier far than these.

2020-05-30

HackerRank - Regex - Grouping and Capturing

Matching Word Boundaries

\b assert position at a word boundary.

Three different positions qualify for word boundaries :

Before the first character in the string, if the first character is a word character.
Between two characters in the string, where one is a word character and the other is not a word character.
After the last character in the string, if the last character is a word character.

Task

Found any match?

1	\b[aeiouAEIOU][a-zA-Z]*\b

Capturing & Non-Capturing Groups

()

Parenthesis () around a regular expression can group that part of regex together. This allows us to apply different quantifiers to that group. This allows us to apply different quantifiers to that group.

These parenthesis also create a numbered capturing. It stores the part of string matched by the part of regex inside parentheses.

These numbered capturing can be used for backreferences.

(?:)

(?:) can be used to create a non-capturing group. It is useful if we do not need the group to capture its match.

For Example

12 34 567 9

1	\s{1}(?=\d+)

Task

okokok! cya

1	(?:ok){3,}

Alternative Matching

Alternations, denoted by the | character, match a single item out of several possible items separated by the vertical bar. When used inside a character class, it will match characters; when used inside a group, it will match entire expressions (i.e., everything to the left or everything to the right of the vertical bar). We must use parentheses to limit the use of alternations.

Task

Mr.DOSHI

1	^(Mr\.\|Mrs\.\|Ms\.\|Dr\.\|Er\.)[a-zA-Z]{1,}$

Resources

Regex - Subdomains - Grouping and Capturing

2020-05-29

Rain

by Robert Louis Stevenson

The rain is raining all around,
It falls on field and tree,
It rains on the umbrellas here,
And on the ships at sea.

2020-05-23

Gauss's algorithm and Chinese remainder theorem

$
\begin{align*}
\begin{cases}
x \equiv 2 \hspace{2mm} (mod \hspace{1mm} 3) \hspace{8mm} 2,5,8,11,14,17,20,\textbf{23},\cdots \\
x \equiv 3 \hspace{2mm} (mod \hspace{1mm} 5) \hspace{8mm} 3,8,13,18,\textbf{23},28,\cdots \\
x \equiv 2 \hspace{2mm} (mod \hspace{1mm} 7) \hspace{8mm} 2,9,16,\textbf{23},30,\cdots
\end{cases}
\end{align*}
$

$ n_1=3, n_2=5, n_3=7 $
$ N = n_1 \times n_2 \times n_3 = 3 \times 5 \times 7 = 105 $
$ a_1=2, a_2=3, a_3=2. $

Now $ N_1 = \frac{N}{n_1} = 35 $ and so $d_1 \equiv 35^{-1} \hspace{2mm} (mod \hspace{1mm} 3) = 2 $,
$ N_2 = \frac{N}{n_2} = 21 $ and so $d_2 \equiv 21^{-1} \hspace{2mm} (mod \hspace{1mm} 5) = 1 $, and
$ N_3 = \frac{N}{n_3} = 15 $ and so $d_3 \equiv 15^{-1} \hspace{2mm} (mod \hspace{1mm} 7) = 1 $. Hence

$ x \equiv (2 \times 35 \times 2) + (3 \times 21 \times 1) + (2 \times 15 \times 1) = 233 ≡ 23 \hspace{2mm} (mod \hspace{1mm} 105) $

The Chinese Remainder Theorem

If the $n_i$ are pairwise coprime, and if $a_1, …, a_k$ are any integers

$
\begin{align}
x \equiv a_1 \hspace{2mm} (mod \hspace{1mm} n_1) \\
x \equiv a_2 \hspace{2mm} (mod \hspace{1mm} n_2) \\
x \equiv a_3 \hspace{2mm} (mod \hspace{1mm} n_3) \\
\vdots \\
x \equiv a_k \hspace{2mm} (mod \hspace{1mm} n_k)
\end{align}
$

has a simultaneous solution which is unique modulo $n_1n_2⋯n_k$.

Gauss’s algorithm

Let $N = \prod_{i=1}^k n_i $ then
$x ≡ \sum_{i=1}^k a_iN_id_i \hspace{2mm} (mod \hspace{1mm} N)$

where $N_i = N/n_i$ and $d_i ≡ N_i^{-1} \hspace{2mm} (mod \hspace{1mm} n_i).$

The latter modular inverse $d_i$ is easily calculated by the extended Euclidean algorithm.

Resources

The Chinese Remainder Theorem

2020-05-22

HackerRank - Regex - Repetitions

Matching {x} Repetitions

The tool {x} will match exactly x repetitions of character/character class/groups.

For Example

w{3} : It will match the character w exactly 3 times.
[xyz]{5} : It will match the string of length 5 consisting of characters {x, y, z}. For example it will match xxxxx, xxxyy and xyxyz.
\d{4} : It will match any digit exactly 4 times.

Task

2222222222aaaaaaaaaa2222222222aaaaaaaaaa13 57

1	^[a-zA-Z02468]{40}[13579\s]{5}$

Matching {x, y} Repetitions

The {x,y} tool will match between x and y (both inclusive) repetitions of character/character class/group.

For Example

w{3,5} : It will match the character w 3, 4 or 5 times.
[xyz]{5,} : It will match the character x, y or z 5 or more times.
\d{1, 4} : It will match any digits 1, 2, 3, or 4 times.

Task

3threeormorealphabets.

1	^\d{1,2}[a-zA-Z]{3,}\.{0,3}$

Matching Zero Or More Repetitions

The * tool will match zero or more repetitions of character/character class/group.

For Example

w* : It will match the character w 0 or more times.
[xyz]* : It will match the characters x, y or z 0 or more times.
\d* : It will match any digit 0 or more times.

Task

14

1	^\d{2,}[a-z][A-Z]$

Matching One Or More Repetitions

The + tool will match one or more repetitions of character/character class/group.

For Example

w+ : It will match the character w 1 or more times.
[xyz]+ : It will match the character x, y or z 1 or more times.
\d+ : It will match any digit 1 or more times.

Task

1Qa

1	^\d+[A-Z]+[a-z]+$

Matching Ending Items

The $ boundary matcher matches an occurrence of a character/character class/group at the end of a line.

Task

Kites

1	^[a-zA-Z]*s$

Resources

Regex - Subdomains - Repetitions