LeetCode - Algorithms - 172. Factorial Trailing Zeroes

Problem

172. Factorial Trailing Zeroes

Java

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

1
2
3
4
5
6
7
8
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

1
2
3
4
5
6
7
8
9
10
11
12
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.

LeetCode - Algorithms - 169. Majority Element

There are many solutions to an easy problem.

Problem

169. Majority Element

Java

sorting

1
2
3
4
5
6
7
8
9
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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

© Approach 6: Boyer-Moore Voting Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
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.

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.

HackerRank - Regex - Grouping and Capturing

© HackerRank

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

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

HackerRank - Regex - Repetitions

© HackerRank

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

LeetCode - Algorithms - 34. Find First and Last Position of Element in Sorted Array

Problem

34. Find First and Last Position of Element in Sorted Array

Java

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
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int lo = 0;
        int hi = nums.length - 1;
        while (lo<=hi) {
            int mid = lo + (hi - lo) / 2;
            if (target < nums[mid])
                hi = mid-1;
            else if (target > nums[mid])
                lo = mid+1;
            else {
                int startPos = mid;
                int endPos = mid;
                while(startPos>=0 && nums[startPos]==nums[mid]) startPos--;
                while(endPos<=nums.length - 1 && nums[endPos]==nums[mid]) endPos++;
                int[] r = new int[2];
                r[0] = startPos+1;
                r[1] = endPos-1;
                return r;
            }
        }

        int[] r = {-1, -1};
        return r;       
    }
}

Submission Detail

  • 88 / 88 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Find First and Last Position of Element in Sorted Array.
  • Memory Usage: 44.5 MB, less than 6.38% of Java online submissions for Find First and Last Position of Element in Sorted Array.

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    var lo = 0, hi = nums.length-1;
    while (lo<=hi) {
        var mid = lo + Math.floor((hi-lo)/2);
        if (target < nums[mid])
            hi = mid-1;
        else if (target > nums[mid])
            lo = mid+1;
        else {
            var startPos = mid, endPos = mid;
            while(startPos>=0 && nums[startPos]==nums[mid]) startPos--;
            while(endPos<=nums.length - 1 && nums[endPos]==nums[mid]) endPos++;
            return [startPos+1, endPos-1];
        }
    }

    return [-1, -1];    
};

Submission Detail

  • 88 / 88 test cases passed.
  • Runtime: 92 ms, faster than 7.49% of JavaScript online submissions for Find First and Last Position of Element in Sorted Array.
  • Memory Usage: 34.9 MB, less than 100.00% of JavaScript online submissions for Find First and Last Position of Element in Sorted Array.

LeetCode - Algorithms - 205. Isomorphic Strings

Problem

205. Isomorphic Strings

Java

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
class Solution {
    public boolean isIsomorphic(String s, String t) {
        boolean r = true;
        Map<Character,Character> map = new HashMap<Character, Character>();
        Map<Character,Character> map2 = new HashMap<Character, Character>();
        for(int i=0; i<s.length(); i++) {
            char k = s.charAt(i);
            char x = t.charAt(i);
            if (map.containsKey(k)) {
                char v = map.get(k);
                if (x!=v) {
                    return false;
                }
            }
            else {
                map.put(k,x);
            }
            if (map2.containsKey(x)) {
                char v = map2.get(x);
                if (k!=v) {
                    return false;
                }
            }
            else {
                map2.put(x, k);
            }
        }
        return r;        
    }
}

Submission Detail

  • 32 / 32 test cases passed.
  • Runtime: 12 ms, faster than 26.96% of Java online submissions for Isomorphic Strings.
  • Memory Usage: 39.6 MB, less than 6.14% of Java online submissions for Isomorphic Strings.

How to Read Code

How to read other people’s code? You will need good code-browsing skills to make sense of the code.

Start by gathering information about which problems the program should solve and which code style to adapt.

Don’t spend all your time figuring out how everything works at the beginning. Narrow things down to something you can actually process.

Step through behavior that concerns you with a debugger. The stack trace have a lot of information about how events are propogated in the application.

In Action

getting it into a “smart” IDE that can make sense of it

try to build and run it (preferably in a debugger)

  • Find Main, Reading “main”

Learn to Dig

git blame

You can use git blame on a file to get an author name, last modified date, and commit hash for every single line.

git log

Use git log to look at the commit history of the overall repo.

git log can also show you the history of a single file with the -p flag: git log -p index.js.

breakpoint

One method the community strongly suggests is to set out breakpoint on methods that triggers behaviours that concerns you. If changing a line of code causes unexpected changes on other places, put a breakpoint on that line, and see what happens. You have a lot of information on the runtime state once the breakpoint hits. Breakpoints stops the execution of the code on a certain line, and from there, you can see from the stacktrace how the code got there. Use the step into and step out functions to see what the different methods does and how events are propogated in the application. This will teach you something about the structure of the codebase.

Grepping

the search function in your IDE

Search for Key Words

Use your editor’s Find feature (or grep) to search the entire source tree for occurrences of words associated with what you want to know. For example, if you want to figure out how/where the program opens files, search for “open” or “file”. You may get zillions of hits, but that’s not a bad thing–a focused reading of the code will result.
Often-useful words for C/C++ programs are “main”, “abort”, “exit”, “catch”, “throw”, “fopen”, “creat”, “signal”, “alarm”, “socket”, “fork”, “select”. Other words are useful in other languages.

Code Review

Software development is a very collaborative work. No one can build a large or a significant software alone. Every software is built in a team. In a team, everyone contributes to shaping a project. End of the day, everyone’s contribution get merged and become a good piece of work which has a real value to the customers.

Besides doing the actual coding, there is another practice that every team these days does, which is, review each other’s code making observations, suggestions and learning from one other. This is a powerful tool for building knowledge of a code base, creating strong bonds in a team and improving code quality that leads to fewer bugs in the system, and happy customers.

Doing code review, you are forced to read someone else’s code in your team which ends up improving your code reading skill.

Things to Remember

Go Back in Time

Read the Specs

Think of Comments as Hints

Commenting your code is incredibly important, for yourself and for your peers reviewing your code.

Notice Style

Expect to Find Garbage

Don’t Get Lost

  • Where is this button?
  • What do the tests do?
  • The graphical layout
  • Runtime Investigation

Find one thing you know the code does, and trace those actions backward, starting at the end.

Let’s call those connected pieces of code a “chain of actions.”

Following input events

Rinse and repeat.

a body of code is designed to tackle one (or more) complex problems.

the more you can gain an understanding of how different parts of the code are connected, the more you’ll develop an understanding of the entire codebase, as a whole.

the more (good) code you see, the easier it becomes to read and understand all code, and the faster you can do so.

“high quality examples of expertise” = good code

exposure to high quantity, high quality examples of expertise is one of the two main factors that dictate how quickly and effectively people learn new skills. – Badass: Making Users Awesome, Kathy Sierra

The more you watch (or listen) to expert examples, the better you can become. The less exposure you have to experts or results of expert work, the less likely you are to develop expert skills.

the longer you’re programming — and thus the more code samples you see, of all different kinds — the easier it gets to understand other people’s code. And the faster you’re able to do it.

Reading a class

Before reading the implementation of a class, however, I recommend you study its interface.

The public functions will most likely be the command interface for your class.

Retelling or Rubber Ducking

Use/know tools

There are plenty of tools out there for reading and exploring source code that can help to visualize code. For example – IntelliJIdea has really a great capability of navigating source code where you can search by words, part of a word or even abbreviation. You should learn the keyboard shortcuts as well. Navigating source code with the mouse can be pretty boring and slow where working with the keyboard shortcuts can be faster. You can jump from one part of the source code to another quickly.

There is another great software to read code, called Sourcegraph, which was created by two Stanford grads, Quinn Slack and Beyang Liu, who, after spending hours hunting through the poorly documented code, decided to build a tool to help them better reading and understanding the code.

Know the language/conventions

Read the best practices/design patterns

Temporary Refactoring

heuristics

Code is not like a novel

if you insist on understanding each and every thing before you understand the next, you will be lost for sure.

Let the machine help

Take the time to learn and use the stepper, trace, inspecting and browsing tools.

Many important relations in a program are non-sequential, and there are tools that will help you find what to look at next.

Start with an example

Don’t try to understand what all the code does at once. Instead, start with a specific example, representative of what a new user might try in his or her first session with the program, or an example from the manual primer.
Set yourself the task of learning just how that particular example works. Ignore everything else that doesn’t pertain to that example.

Go just as deep as you have to do to understand it, no deeper. Treat everything else as a black box. Learn about how it works later.

Become familiar with the user interface from a user’s perspective. For each user-visible action or object, ask: “Where is that implemented”?

Have a specific goal in mind when you work. Experiment with small changes and extensions to the code to test your understanding.

If it ain’t broke, fix it

The best attitude to take is to pretend you are debugging the code, even if there is nothing wrong with it. The same tools that are used for debugging the code will be helpful in getting you to understand it in the first place. Even if you aren’t looking for bugs now, if you plan on using, extending or modifying the code, you soon will be.

Tools

  • Jump to function definition
  • Step the code
  • Guess function names
  • Trace functions
  • Inspect the application’s data structures

RTFM

When all else fails, read the documentation.

another invaluable tool is stored inside your browser: the Developer tools. Knowing how to use the developer tools correctly and effectively can help you quickly locate the source of problems with styling these sections.

localized JavaScript console, where you can test out code separately from your programs.

Start with what you do know

find one thing you know the code does, and trace those actions backward, starting at the end.

Believe that you know what you’re looking at

For ultimately effective searching, you’ll want to use something like “language_name function_name” in your Google search, rather than just the function name, as they can be repetitive across multiple coding languages.

In the long run, expose yourself to high-quality code

By exposing yourself to well-written code made by experienced programmers, you are subconsciously taking in the methodology they follow, as well as their best practices.

If you read poorly-written, non-semantic code, you will likely emulate the same when writing your own. And yes, although we all start writing garbage code, our ultimate goal is to move on from that point as quickly as possible!

Try watching live-streamed programming (or pair programming with a peer)

it’s one of the best ways to watch the coding process from start to finish in real time, and ask questions as you encounter them. Watching other people program in real time also gives you insight into other people’s coding processes, and helps you develop good habits, regardless of whether or not they are a master themselves.

For an excellent resource on the front end (HTML, CSS, JavaScript), try perusing Codepen. Free, and very user-friendly, many front-end developers use this site as a sandbox.

On the back end, I recommend you sign up for GitHub and start digging into some of the most popular repositories. You can view a file from right within your browser, and if you wish to improve on the code, you can edit it in your own forked version and create a “pull request”. If the author likes your improvements, they may choose to implement them into their programs!

Find the high-level logic

Starting with the program’s entry point (e.g. main() in C/C++/Java), find out how the program initializes itself, does its thing, and then terminates.

Basically, skimmed through the whole project and gain a primary idea and then ask a question to yourself where do you want to focus, which part you want to read first.

Draw Some Flowcharts

Yes, we all know flowcharts are a horrible design tool, but they can be useful when analyzing program flow. You can’t keep all that information in your head, so draw some flowcharts or state diagrams while you are reading. Make sure you account for both sides of a two-way branch, and all branches of multi-way branches.

Examine Library Calls

Leverage the Power of Code Comprehension Tools

Some techniques available with a good text search tool, or better yet a tool that can analyze the source and find references and generate diagrams, allow the following questions to be answered, for object-oriented code:

  • Who calls this method?
  • Who implements this interface or subclasses this class?
  • What are this class’ superclasses?
  • Where are instances of this class created, held, and passed as arguments or returned?
  • What superclass methods does this class override?
  • Where might methods of this class be called polymorphically, i.e. through a base class or interface?

developing a “big picture” view of the code

reading and writing tests

Although testing is rare, it acts as a wonderful documentation tool, and is a good introduction to a new codebase.

Comment the Code

One of the best ways of reverse-engineering code you’re so unfamiliar with that you cannot even guess to comment is to derive HoareTriples for the code under scrutiny, and to compute a procedure’s WeakestPrecondition. Knowing the invariants of a procedure often gives valuable clues as to its intended purpose, thus letting you derive understanding from the code in a way that merely guessing from reading a number of poorly named procedure names simply cannot. Using this technique, you might even find bugs in the code, despite your lack of understanding thereof (I know this from experience!).

Clean Up the Code

Use Aspect Browser

Aspect Browser is a tool for viewing cross-cutting code aspects in large amounts of code. I find it indispensable for navigating unfamiliar code, as a kind of super-grep.

AspectBrowser for Eclipse

Resources