Problem

268. Missing Number

Java

leetcode solution

© Approach 3 Bit Manipulation

1
2
3
4
5
6
7
8
9

class Solution {
    public int missingNumber(int[] nums) {
        final int N = nums.length;
        int r = N;
        for (int i = 0; i < N; i++)
            r ^= i ^ nums[i];
        return r;        
    }
}

Submission Detail

• 122 / 122 test cases passed.
• Runtime: 0 ms, faster than 100.00% of Java online submissions for Missing Number.
• Memory Usage: 47.8 MB, less than 5.40% of Java online submissions for Missing Number.

2

© Bitwise operators — Facts and Hacks - Compute XOR from 1 to n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int missingNumber(int[] nums) {
        final int N = nums.length;
        int x = computeXOR(N);
        x = 0 ^ x;
        int y = nums[0];
        for (int i = 1; i < N; i++) {
            y = y ^ nums[i];
        }
        return x ^ y;        
    }
    
    private int computeXOR(int n) {
        if (n % 4 == 0) return n;
        if (n % 4 == 1) return 1;
        if (n % 4 == 2) return n + 1;
        else return 0;
    }
}

Submission Detail

• 122 / 122 test cases passed.
• Runtime: 1 ms, faster than 40.83% of Java online submissions for Missing Number.
• Memory Usage: 48 MB, less than 5.40% of Java online submissions for Missing Number.

Problem

136. Single Number

Java

Hash Set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int singleNumber(int[] nums) {
        Set<Integer> c = new HashSet<Integer>();
        for (int i : nums) {
            if (c.contains(i))
                c.remove(i);
            else
                c.add(i);
        }
        return c.iterator().next();        
    }
}

Submission Detail

• 61 / 61 test cases passed.
• Runtime: 8 ms, faster than 42.20% of Java online submissions for Single Number.
• Memory Usage: 39.8 MB, less than 22.36% of Java online submissions for Single Number.

sorting

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        final int N = nums.length;
        if (N == 1)
            return nums[0];
        if (nums[0] != nums[1])
            return nums[0];
        if (nums[N - 1] != nums[N - 2])
            return nums[N - 1];
        for (int i = 1; i < N - 1; i++) {
            if (nums[i] != nums[i + 1] && nums[i] != nums[i - 1]) {
                return nums[i];
            }
        }
        return nums[0];       
    }
}

Submission Detail

• 61 / 61 test cases passed.
• Runtime: 5 ms, faster than 54.05% of Java online submissions for Single Number.
• Memory Usage: 39.2 MB, less than 69.77% of Java online submissions for Single Number.

XOR Bitwise

n ^ n = 0

n ^ 0 = n

1
2
3
4
5
6
7
8
9

class Solution {
    public int singleNumber(int[] nums) {
        int r = nums[0];
        for (int i = 1; i < nums.length; i++) {
            r = r ^ nums[i];
        }
        return r;       
    }
}

Submission Detail

• 61 / 61 test cases passed.
• Runtime: 1 ms, faster than 94.97% of Java online submissions for Single Number.
• Memory Usage: 39.1 MB, less than 79.60% of Java online submissions for Single Number.

java8 stream + xor bitwise

1
2
3
4
5

class Solution {
    public int singleNumber(int[] nums) {
        return Arrays.stream(nums).reduce(0, (a, b) -> a^b);      
    }
}

Submission Detail

• 61 / 61 test cases passed.
• Runtime: 2 ms, faster than 55.66% of Java online submissions for Single Number.
• Memory Usage: 39.2 MB, less than 69.77% of Java online submissions for Single Number.

Problem

976. Largest Perimeter Triangle

Java

1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {    
    public int largestPerimeter(int[] A) {
        Arrays.sort(A);
        int a, b, c;
        for (int i = A.length - 1; i >= 2; i--) {
            a = A[i - 2];
            b = A[i - 1];
            c = A[i];
            if (a + b > c) {
                return a + b + c;
            }
        }
        return 0;       
    }
}

Submission Detail

• 84 / 84 test cases passed.
• Runtime: 6 ms, faster than 99.79% of Java online submissions for Largest Perimeter Triangle.
• Memory Usage: 39.4 MB, less than 76.17% of Java online submissions for Largest Perimeter Triangle.

Problem

1137. N-th Tribonacci Number

Java

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int tribonacci(int n) {
        int T = 0;
        int T1 = 0, T2 = 1, T3 = 1;
        if (n == 0)
            T = 0;
        if (n == 1)
            T = 1;
        if (n == 2)
            T = 1;
        for (int i = 3; i <= n; i++) {
            T = T1 + T2 + T3;
            T1 = T2;
            T2 = T3;
            T3 = T;
        }
        return T;
    }
}

Submission Detail

• 39 / 39 test cases passed.
• Runtime: 0 ms, faster than 100.00% of Java online submissions for N-th Tribonacci Number.
• Memory Usage: 35.8 MB, less than 47.18% of Java online submissions for N-th Tribonacci Number.

Problem

1360. Number of Days Between Two Dates

Java

Origin-based algorithm

© Algorithms for calculating the difference of dates in days - 4. Origin-based Algorithm

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

class Solution {
    final static int[] daysUpToMonth = {0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334};
    final static int[] daysUpToMonthLeapYear = {0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335};

    public boolean isLeapYear(int year) {
        return (year % 4 == 0) && ((year % 100 != 0) || (year % 400 == 0));
    }
    
    public int GetDaysOffsetFromOrigin(int year, int month, int day) {
        if (isLeapYear(year)) {
            year--;
            int numOfLeapsYear = year / 4 - year / 100 + year / 400;
            return year * 365 + numOfLeapsYear + daysUpToMonthLeapYear[month - 1] + day - 1;
        } else {
            year--;
            int numOfLeapsYear = year / 4 - year / 100 + year / 400;
            return year * 365 + numOfLeapsYear + daysUpToMonth[month - 1] + day - 1;
        }
    }    
    
    public int daysBetweenDates(String date1, String date2) {
        int y1 = Integer.parseInt(date1.substring(0, 4));
        int m1 = Integer.parseInt(date1.substring(5, 7));
        int d1 = Integer.parseInt(date1.substring(8, 10));

        int y2 = Integer.parseInt(date2.substring(0, 4));
        int m2 = Integer.parseInt(date2.substring(5, 7));
        int d2 = Integer.parseInt(date2.substring(8, 10));

        int daysOffset = GetDaysOffsetFromOrigin(y1, m1, d1);
        int daysOffset2 = GetDaysOffsetFromOrigin(y2, m2, d2);

        int diff = daysOffset2 - daysOffset;

        return diff >= 0 ? diff : -diff;        
    }
}

Submission Detail

• 105 / 105 test cases passed.
• Runtime: 0 ms, faster than 100.00% of Java online submissions for Number of Days Between Two Dates.
• Memory Usage: 37.1 MB, less than 71.69% of Java online submissions for Number of Days Between Two Dates.

jdk

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

import java.time.LocalDate;
import java.time.format.DateTimeFormatter;

import static java.time.temporal.ChronoUnit.DAYS;

class Solution {
    public int daysBetweenDates(String date1, String date2) {
        DateTimeFormatter dft = DateTimeFormatter.ofPattern("yyyy-MM-dd");
        LocalDate d1 = LocalDate.parse(date1, dft);
        LocalDate d2 = LocalDate.parse(date2, dft);
        long diff = DAYS.between(d1, d2);
        int d = new Long(diff).intValue();
        return d >= 0 ? d : -d;        
    }
}

Submission Detail

• 105 / 105 test cases passed.
• Runtime: 14 ms, faster than 13.23% of Java online submissions for Number of Days Between Two Dates.
• Memory Usage: 38.4 MB, less than 21.16% of Java online submissions for Number of Days Between Two Dates.

© FSI’s Experience with Language Learning

The following language learning timelines reflect 70 years of experience in teaching languages to U.S. diplomats, and illustrate the time usually required for a student to reach “Professional Working Proficiency” in the language, or a score of “Speaking-3/Reading-3” on the Interagency Language Roundtable scale. These timelines are based on what FSI has observed as the average length of time for a student to achieve proficiency, though the actual time can vary based on a number of factors, including the language learner’s natural ability, prior linguistic experience, and time spent in the classroom.

Category I Languages: 24-30 weeks (600-750 class hours)

Languages more similar to English.

• Danish (24 weeks)
• Dutch (24 weeks)
• French (30 weeks)
• Italian (24 weeks)
• Norwegian (24 weeks)
• Portuguese (24 weeks)
• Romanian (24 weeks)
• Spanish (24 weeks)
• Swedish (24 weeks)

Category II Languages: Approximately 36 weeks (900 class hours)

• German
• Haitian Creole
• Indonesian
• Malay
• Swahili

Category III Languages: Approximately 44 weeks (1100 class hours)

“Hard languages” – Languages with significant linguistic and/or cultural differences from English. This list is not exhaustive.

• Albanian
• Amharic
• Armenian
• Azerbaijani
• Bengali
• Bulgarian
• Burmese
• Czech
• Dari
• Estonian
• Farsi
• Finnish
• Georgian
• Greek
• Hebrew
• Hindi
• Hungarian
• Icelandic
• Kazakh
• Khmer
• Kurdish
• Kyrgyz
• Lao
• Latvian
• Lithuanian
• Macedonian
• Mongolian
• Nepali
• Polish
• Russian
• Serbo-Croatian
• Sinhala
• Slovak
• Slovenian
• Somali
• Tagalog
• Tajiki
• Tamil
• Telugu
• Thai
• Tibetan
• Turkish
• Turkmen
• Ukrainian
• Urdu
• Uzbek
• Vietnamese

Category IV Languages: 88 weeks (2200 class hours)

“Super-hard languages” – Languages which are exceptionally difficult for native English speakers.

• Arabic
• Chinese – Cantonese
• Chinese – Mandarin
• Japanese
• Korean

IELTS Academic mean performance by first language

IELTS Academic mean performance by nationality

• IELTS Test taker performance 2019
• IELTS Demographic data 2019

Problem

167. Two Sum II - Input array is sorted

Java

Brute-force

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        final int N = numbers.length;
        int[] idxArr = {0, 0};
        for (int i = 0; i < N; i++)
            for (int j = N - 1; j > i; j--) {
                if (numbers[j] + numbers[i] == target) {
                    idxArr[0] = i + 1;
                    idxArr[1] = j + 1;
                    return idxArr;
                }
            }
        return idxArr;
    }
}

Submission Detail

• 17 / 17 test cases passed.
• Runtime: 191 ms, faster than 7.92% of Java online submissions for Two Sum II - Input array is sorted.
• Memory Usage: 39.6 MB, less than 16.46% of Java online submissions for Two Sum II - Input array is sorted.

binary search

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

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        final int N = numbers.length;
        int index1 = 0, index2 = 0;
        for (int i = 0; i < N / 2 + 1; i++) {
            index1 = i;
            int diff = target - numbers[i];
            int lo = 0;
            int hi = i - 1;
            if (diff >= numbers[i]) {
                lo = i + 1;
                hi = N - 1;
            }
            index2 = search_rank(numbers, lo, hi, diff);
            if (index2 > -1) {
                index1++;
                index2++;
                break;
            }
        }
        return new int[]{index1, index2};
    }

    public int search_rank(int[] nums, int lo, int hi, int target) {
        // Array must be sorted.
        while (lo <= hi) {
            // Key is in a[lo..hi] or not present.
            int mid = lo + (hi - lo) / 2;
            if (target < nums[mid])
                hi = mid - 1;
            else if (target > nums[mid])
                lo = mid + 1;
            else
                return mid;
        }
        return -1;
    }
}

Submission Detail

• 17 / 17 test cases passed.
• Runtime: 2 ms, faster than 21.89% of Java online submissions for Two Sum II - Input array is sorted.
• Memory Usage: 39.2 MB, less than 45.66% of Java online submissions for Two Sum II - Input array is sorted.

Two Pointer

Algorithm Two Pointer Technique:

The two pointer technique is a useful tool to utilize when searching for pairs in a sorted array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        final int N = numbers.length;
        for (int lo = 0, hi = N - 1; lo < hi; ) {
            if (numbers[lo] + numbers[hi] > target)
                hi--;
            else if (numbers[lo] + numbers[hi] < target) {
                lo++;
            } else {
                return new int[]{lo + 1, hi + 1};
            }
        }
        return new int[]{0, 0};
    }
}

Submission Detail

• 17 / 17 test cases passed.
• Runtime: 0 ms, faster than 100.00% of Java online submissions for Two Sum II - Input array is sorted.
• Memory Usage: 39.4 MB, less than 33.74% of Java online submissions for Two Sum II - Input array is sorted.

This land is your land, This land is my land,
From Bonavista, to Vancouver Island
From the Arctic Circle to the Great Lakes waters,
This land was made for you and me.

As I went walking that ribbon of highway,
I saw above me that endless skyway;
I saw below me that golden valley
This land was made for you and me.

I roamed and I rambled and I followed my footsteps,
To the sparkling sands of her diamond deserts;
While all around me a voice was sounding,
Saying this land was made for you and me.

The sun came shining, and I was strolling,
And the wheat fields waving and the dust clouds rolling;
As the fog was lifting, a voice was chanting,
This land was made for you and me.

This land is your land, this land is my land,
From Bonavista to Vancouver Island;
From the Arctic Circle to the Great Lakes waters,
This land was made for you and me.

• This Land Is Your Land
• Woody Guthrie
• This version was written and popularized by Canadian folk music group The Travellers in 1955.

Merriam-Webster

Merriam-Webster’s Word of the Year for 2020 is pandemic.

Collins

‘Lockdown’, the containment measure implemented by governments around the world to mitigate the spread of COVID-19, has been named the Collins Word of the Year 2020.

Oxford Dictionaries - Words of an unprecedented year

Oxford Languages concluded that this is a year which cannot be neatly accommodated in one single word.

The language of Covid-19

Coronavirus, Covid-19, and related words

By March this year coronavirus was one of the most frequently used nouns in the English language

Pandemic and other -demics

An epidemic is a disease which is widespread in a community; a pandemic is one which has spread much more widely, across a whole country, multiple countries, or the whole world.

Social distancing, lockdown, and other measures

In March this year, as governments across the world introduced measures to reduce the spread of Covid-19, social distancing – along with the related verb socially distance and the adjective socially distanced – surged in frequency.

Masks and coverings

Mask-shaming is especially interesting as it is a contronym which has two opposite meanings

Epidemiological terms

Other terms which have become much more common this year in everyday discourse include flatten the curve and community transmission.

An important aspect of reducing transmission is eliminating superspreader events.

On the frontline

Other very significant words of the year are those relating to the medical response to Covid-19, including PPE (and its fuller form personal protective equipment) and ventilator. There has also been a recognition of medical staff and other workers providing an essential service, often referred to as key workers (especially in the UK), essential workers (especially in the US), or frontline workers.

World Englishes

Most lexical innovation happened this year as a reaction to the Covid-19 pandemic

A particularly noteworthy example is circuit breaker, a term originally referring to a safety device that stops the flow of current in an electric circuit, and later also in widespread use as a piece of financial slang for a regulatory instrument designed to prevent panic selling by temporarily stopping trading on an exchange.

At the outset of the Covid-19 pandemic, a Southeast Asian word suddenly gained global prominence: wet market.

Faced with the challenges of providing face-to-face classroom teaching, the education sector in many countries turned to technology: e-learning has become a widely used term in Africa and Asia; in Southeast Asia, there has been much discussion on new learning modalities; and more widely blended learning which combines online with in-person instruction has seen a significant increase in usage.

Technology and remote working

The lockdown accelerated the move towards flexible, remote working

The environment

One of the defining climatic events of the end of 2019 and beginning of 2020 was the Australian bushfire season, the worst on record. The word bushfire surged in frequency in January, and was one of the top keywords in our corpus that month.

In March this year, the frequency of climate, global warming, and related terms plummeted in our corpus.

Climate and related terms are becoming more frequent again, while net zero (another word on our 2019 Word of the Year shortlist, referring to a target of completely negating the amount of greenhouse gases produced by human activity) is also on the rise: the recent increase partly relates to the historic pledge made by President Xi Jinping in September, that China will be carbon neutral by 2060.

Social movements and social media

the term Black Lives Matter, and its abbreviation BLM, exploded in usage beginning in June of this year

there has been a surge in usage of D&I, an abbreviation of diversity and inclusion, as well as BIPOC, an abbreviation of black, indigenous, and other people of colour.

we noted increases in the term cancel culture, the culture of boycotting and withdrawing support from public figures whose words and actions are considered socially unacceptable, as well as the use of Karen as a generic name for a white woman who behaves in a stereotypically racist or discriminatory manner.

Politics and economics

impeachment was a hot topic, and was one of the keywords in our corpus in January when the trial to impeach Donald Trump began. Acquittal peaked in February at the conclusion of the trial.

Furlough was originally associated with members of the armed forces going on leave, and was chiefly used in the US. In March and April 2020 though, when it started to be used in other countries as employers were given grants to pay employees who were not working, usage shot up.

Elsewhere our language use highlights the story of the shocking economic impact of the crisis. Words showing significant increase in use include stimulus, unemployment, layoff, and eviction.

• Word of the Year 2020
• Merriam-Webster’s Word of the Year 2020
• The Collins Word of the Year 2020 is…
• OED Word of the Year expanded for ‘unprecedented’ 2020
• “前所未有的2020年”：牛津字典年度热词不止一个

by W. A. Hurwitz with no apologies to Gilbert and Sullivan

When I was a kid and went to school,
Arithmetic was only taught by rote and rule.
I did long division and I took cube root;
At the rule of three I was especially astute.
I was so astute at the rule of three
That now I am the holder of the Ph.D.

Chorus:
He was so astute at the rule of three
That now he is the holder of the Ph.D.

In algebra, later, I learned nice words
Like TRANSPOSE, CANCEL, and REMOVE THE SURDS.
DIVIDE BOTH SIDES BY z OR y;
That either might be zero didn’t make me sigh.
I cared so little if zero was z
That now I am the holder of the Ph.D.

Chorus:
He cared so little if zero was z
That now he is the holder of the Ph.D.

In geometry, too, I made such a mark
That my classmates called me a regular shark.
I memorized theorems through and through;
Originals I never was required to do.
Originals useless seemed to me
So now I am the holder of the Ph.D.

Chorus:
Originals useless seemed to him
So now he is the holder of the Ph.D.

In college, of course, I played my part;
I majored in Math from the very start.
It didn’t much matter if I learned the stuff;
I only had to manage a successful bluff;
I managed to bluff so successfully
That now I am the holder of the Ph.D.

Chorus:
He managed to bluff so successfully
That now he is the holder of the Ph.D.

The faculty said I was such a jerk,
I was obviously destined for graduate work.
They gave me a job so I could earn some pelf
By teaching younger morons who were like myself.
I taught those morons with such esprit
That now I am the holder of the Ph.D.

Chorus:
He taught those morons with such esprit
That now he is the holder of the Ph.D.

My graduate work I took in stride;
If I couldn’t prove a theorem I just let it ride.
With grades of C I was quite content,
But now and then I made a B by accident.
So frequently by accident I made a B
That now I am the holder of the Ph.D.

Chorus:
So frequently by accident he made a B
That now he is the holder of the Ph.D.

They had a silly rule that a thesis was required,
So I sought a kind professor whose assistance I desired.
He said, “Do this” and he said, “Do that”
And he had my thesis finished up in three months flat.
It wasn’t a brilliant thesis, but it didn’t have to be,
So now I am the holder of the Ph.D.

Chorus:
It wasn’t a brilliant thesis, but it didn’t have to be,
So now he is the holder of the Ph.D.

I still had to take an oral exam;
My only preparation was to cram, cram, cram.
The profs all said I made a very poor show,
But I knew as much at present as I ever would know.
To get me off their hands, they gave me a degree,
So now I am the holder of the Ph.D.

Chorus:
To get him off their hands, they gave him a degree,
So now he is the holder of the Ph.D.

Now math students all, both far and near,
If you want to seek an academic life career,
And you don’t want to teach in a secondary school,
Be guided by this golden rule:
Never try to show originality,
And you each may be the holder of the Ph.D.

Chorus:
Never try to show originality,
And you each may be the holder of the Ph.D.

Elon Musk

A PhD is definitely not required. All that matters is a deep understanding of AI & ability to implement NNs in a way that is actually useful (latter point is what’s truly hard). Don’t care if you even graduated high school.

Freeman Dyson

Oh, yes. I’m very proud of not having a Ph.D. I think the Ph.D. system is an abomination. It was invented as a system for educating German professors in the 19th century, and it works well under those conditions. It’s good for a very small number of people who are going to spend their lives being professors. But it has become now a kind of union card that you have to have in order to have a job, whether it’s being a professor or other things, and it’s quite inappropriate for that. It forces people to waste years and years of their lives sort of pretending to do research for which they’re not at all well-suited. In the end, they have this piece of paper which says they’re qualified, but it really doesn’t mean anything. The Ph.D. takes far too long and discourages women from becoming scientists, which I consider a great tragedy. So I have opposed it all my life without any success at all.

I was lucky because I got educated in World War II and everything was screwed up so that I could get through without a Ph.D. and finish up as a professor. Now that’s quite impossible. So, I’m very proud that I don’t have a Ph.D. and I raised six children and none of them has a Ph.D., so that’s my contribution.

• “Ph.D.”
• At 90, Freeman Dyson Ponders His Next Challenge
• Do you agree with Elon Musk that doing Ph.D. would be a waste of time as you would just end up publishing few papers that no one will read?
• https://twitter.com/elonmusk/status/1224089444963311616
• Why doing a PhD is often a waste of time - The disposable academic
• The illustrated guide to a Ph.D.