Interesting mod problem

in Uncategorized | No Comments »

Found an interesting problem on hackerrank(, the problem actually requires you to find an N digits largest “decent number” with:

1. 3, 5, or both as its digits. No other digit is allowed.
2. Number of times 3 appears is divisible by 5.
3. Number of times 5 appears is divisible by 3.

One trivial approach is iterate from 1 to N/5 to find the smallest number of k that after subtracting the k*5 from n, the rest can be divisible by 3 ((n-k*5)%3==0), if not, then return -1.

This solution will take O(c) for one input, actually is O(2000) because the N is less than 100000. Unfortunately, when using Java, half of the test case will exceed the time limit (FML it works for C/C++).

Interestingly, I saw another approach on the discussion form that takes significantly less time than the previous, when an input divide by 3, there will be 3 cases:

case1: the remainder is 0, then we can simply output all 5.
case2: the remainder is 1, after subtracting 10, the output should be divisible by 3, or output -1
case3: the remainder is 2, after subtracting 5, the output should be divisible by 3, or output -1

the code:

Bit Manipulation on Leetcode

in Uncategorized | No Comments »

1. Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1′ bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11′ has binary representation 00000000000000000000000000001011, so the function should return 3.


A sample one, at first glance, my code is like converting the unsigned int to binary and counting the number ones, as follow.

But sadly it did not pass the Leetcode’s OJ with a Wrong answer error when the input int is 2147483648 (10000000000000000000000000000000), well the range of int in Java is -2147483648 to 2147483647, apparently 2147483648 is out the range of signed int but still a 32bit unsigned int, but there is no unsigned int data type in Java, there must be some problems in Leetcode’s OJ.

We can still solve this problem by using bit rotate as follow:

Also there is a fancy way to do the bit rotation:

The running time of the following approaches should be O(C).

TO be continued

LeetCode Two Sum I and II

in Uncategorized | 2 Comments »

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution

The first and the simplest solution is apparently O(n^2) brute force method, which using two nested for loop to find if there is any pair of two numbers in the array added up to the target, which is not the solution we want.

If we could build up a hash table using the numbers in the array as the key and using index in the array as the value which only takes O(1) time to find the key(numbers) equal to target – numbers[i], so it will only take O(n) time to traverse all the array to find the other number which added up to the target.

First we put all the <key,value> in the hash table, then we traverse the arrays to find if there exists a key which is exactly target – numbers[i], then we return i+1 and the value of that key +1. (+1 because non-zero based.) The running time is O(2*n).

the running time in Leetcode is 332 ms.

There is a better version of this hash implementation (at least looks fancy), we can put the table building and checking target number in the same for loop,

The running time should be as same as the first one.

Actually we can perform a sorting to the array, then comes to the sorted version of this problem:

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Solution 1:
Step 1. use two indices for the array, one is in the top(smallest number) the other in the tail(largest number):
Step 2. Check if two numbers of the indices are added up to the target, if the sum is larger than the target, then reduce the tail index, if the sum is smaller than the taget, increase the top index, repeat the step 2 until they sum up to the target, or top index equals to the tail, which means can not find.

This Solution should take O(n) time and O(1) space.

The running time in the Leetcode is 346 ms.

There is also another solution which will take O(n) time but O(n) space,

Step 1, Check if there is two copies of target/2 in the array, if yes, return these two indices.
Step 2, eliminate the same numbers in the array.
Step 3, subtract the target from every number in the array, take the abs value of the number but keep track which number is negative, name this array S’
Step 4, Put S’ and S in the same array with size of double, namely S2, sort S2, check if there is same two numbers in S2 and one of the number is come from S and is originally kept tracking as negative, then return these two indices.

The running time for Step 1, Step 2, Step 3 are all O(n), the step 4 is O(nlogn). So the running time is O(nlogn).

Actually we don’t need to create another array S’, the only thing we need to do is applying binary search over the sorted array finding if exists target-number[i], which is also O(nlogn)

The running time in Leetcode is 312 ms.

Differences between Hashmap and Hashtable in JAVA

in Uncategorized | No Comments »

When it comes to the detail implementation of hash in Java, I’m always confused with the hashmap and hashtable, which one should be used?

Below is a good solution comes from Stack overflow by Josh Brown (

There are several differences between HashMap and Hashtable in Java:

  1. Hashtable is synchronized, whereas HashMap is not. This makes HashMap better for non-threaded applications, as unsynchronized Objects typically perform better than synchronized ones.
  2. Hashtable does not allow null keys or values. HashMap allows one null key and any number of null values.
  3. One of HashMap’s subclasses is LinkedHashMap, so in the event that you’d want predictable iteration order (which is insertion order by default), you could easily swap out the HashMap for a LinkedHashMap. This wouldn’t be as easy if you were using Hashtable.

Since synchronization is not an issue for you, I’d recommend HashMap. If synchronization becomes an issue, you may also look at ConcurrentHashMap.

墨西哥Merida 梅里达续签F1攻略整理

in Uncategorized | No Comments »







1、 填写完DS160表格后,需要进墨西哥的美国签证预约网站填写信息、付签证费和约签证(,在填写信息时,表格的最后一栏有点奇怪,问的是 “Is the applicant traveling from another country to apply for a visa in Mexico? *”, 这里要填yes,不然就默认你是墨西哥人,就不让你面试了(免面试),但是显然我们是需要面试的,而且面试也会加快签证办理的速度。



Merida visa



如果你是坐大巴从坎昆来的梅里达,那巴士站就在红框下面的那个星这儿,可以把酒店订在附近,这样去ASC和大使馆都可以不用打车 直接走过去了。



Por 67 y 69
Calle 66 561-D
97000 Mérida, Yuc., Mexico



X 58 A Y 56 A
Calle 60 338 K
Alcala Martin
97050 Mérida, Yuc., Mexico

Hello world!

in Uncategorized | No Comments »




然后我绞尽脑汁也想不出来当时写了啥,好像提到了 以及还提到了扣扣空间



坎昆是个好地方就是我来的不是时候啊别人都是冬天来过冬 可是现在是墨西哥最热的时候。。。



哦对,为了补完这个第一篇博客 还得传一张照片




© 2016 Hengxiugao's Site - Powered by Wordpress / Theme: Tabinikki