It is Friday and not a hot as it has been in the couple last weeks. The forecast calls for a high around 88F. We will see if the forecast matches the observed temperatures for the day.
The cleaning lady and crew are expected today. Apparently last week she had some issues which ended in a no show.
Due to the fact that I usually talk on Fridays at 07:00 AM with a friend that we met while attending elementary school, my wife and I decided to postpone our daily walk to around lunch. It turns out that my friend had to get up quite early today and travel for business for about two hours. We both are morning people but getting up around 03:00 AM to chat is not acceptable.
Since the cleaning crew will be leaving around lunch time, and my wife and I will go out for a walk, she will not have time to cook lunch which is our main meal of the day. On our way back I will pick up a bag of Asian food from Trader Joe’s which we keep in the outside fridge. Hopefully it will be Kung Pao Chicken. It is our favorite. That said; we typically alter the meal to our taste by adding different things (i.e., chicken broth, unsalted peanuts).
Yesterday I read a very interesting article on IEEE SPECTRUM titled How Software Is Eating the Car. The complexity of software and the amount of features depending on it is growing exponentially. I have had the opportunity to owning several German made cars and have experienced the increase of features and hardware referenced in the article.
Today I decided to tackle a Dynamic Programming problem at LeetCode named LeetCode 338 Counting Bits.
Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i. Constraints: o 0 <= n <= 105 Follow up: * It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass? * Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?
We are given an integer in the specified range. We are required to write a function that returns an array holding the number of 1’s for each value in the range [0 : n]. We will try the brute force approach and then a dynamic programming one using tabulation (not memoization).
We will solve the problem using the Java programming language and the VSCode IDE on a Windows 10 machine. As soon as I am done experimenting with dynamic programming problems I am planning on experimenting with graphs and will switch to using the C++ programming language.
public int[] countBits(int n) {
}
The signature for the function of interest is quite simple and as expected. We get an integer and return an array of integers. Each entry in the array should contain the count of 1-bits in the specified range [0 : n].
Since I will not be using the LeetCode IDE, I will also have to generate some test code to collect the input value, call the function of interest and display the result.
0 main <<< n: 0 main <<< bruteForce: [0] main <<< time: 4900 ns. main <<< countBits: [0] main <<< time: 6800 ns. 2 main <<< n: 2 main <<< bruteForce: [0, 1, 1] main <<< time: 6300 ns. main <<< countBits: [0, 1, 1] main <<< time: 7500 ns. 5 main <<< n: 5 main <<< bruteForce: [0, 1, 1, 2, 1, 2] main <<< time: 5400 ns. main <<< countBits: [0, 1, 1, 2, 1, 2] main <<< time: 8400 ns. 8 main <<< n: 8 main <<< bruteForce: [0, 1, 1, 2, 1, 2, 2, 3, 1] main <<< time: 6700 ns. main <<< countBits: [0, 1, 1, 2, 1, 2, 2, 3, 1] main <<< time: 11800 ns. 11 main <<< n: 11 main <<< bruteForce: [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3] main <<< time: 7100 ns. main <<< countBits: [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3] main <<< time: 6700 ns. 31 main <<< n: 31 main <<< bruteForce: [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5] main <<< time: 10400 ns. main <<< countBits: [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5] main <<< time: 5400 ns. 105 main <<< n: 105 main <<< bruteForce: [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4] main <<< time: 21900 ns. main <<< countBits: [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4] main <<< time: 9100 ns.
The LeetCode website provides two examples. I added a few more.
Our test code reads the input line holding the value for `n`. After reading and assigning the value to a variable, for sanity check reasons, the value is displayed.
As previously stated, we have two implementations of the function in question. The first is the brute force approach. LeetCode accepted our implementation.
The second approach uses tabulation in a dynamic programming approach.
In addition the execution times of each of the test case are displayed.
While we look at the code, we will be referencing the test case with `n` value of 8.
Hint: You should make use of what you have produced already.
LeetCode provides three hints. The first one tells me that we should go with the tabulation approach using dynamic programming. We could have use recursion with and without memoization, but decided to skip such approach.
/**
* Test scaffold
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** initialization ****
long start = 0;
long end = 0;
int[] ans = null;
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read n ****
int n = Integer.parseInt(br.readLine().trim());
// **** check top limit ****
if (n > 105)
n = 105;
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< n: " + n);
// **** compute and display result ****
start = System.nanoTime();
ans = bruteForce(n);
end = System.nanoTime();
System.out.println("main <<< bruteForce: " + Arrays.toString(ans));
System.out.println("main <<< time: " + (end - start) + " ns.");
// **** compute and display result ****
start = System.nanoTime();
ans = countBits(n);
end = System.nanoTime();
System.out.println("main <<< countBits: " + Arrays.toString(ans));
System.out.println("main <<< time: " + (end - start) + " ns.");
}
The test scaffold is quite simple. It matches our description of the test cases. At this point I do not have anything to add to document the code.
/**
* Given an integer n, return an array ans of length n + 1 such that
* for each i (0 <= i <= n),
* ans[i] is the number of 1's in the binary representation of i.
*
* Brute force approach.
*
* Time: O(n * log(n)) - Space: O(n)
*
* Runtime: 8 ms, faster than 15.76% of Java online submissions.
* Memory Usage: 43.1 MB, less than 64.72% of Java online submissions.
*/
static int[] bruteForce(int n) {
// **** sanity checks ****
if (n == 0) return new int[0];
// **** initialization ****
int[] ans = new int[n + 1];
// **** loop computing answer ****
for (int i = 0; i <= n; i++) {
// **** for ease of use ****
int num = i;
// **** loop counting bits set to 1 ****
int count = 0;
for ( ; num != 0; num >>= 1) {
if (num % 2 == 1)
count++;
}
// **** update answer array ****
ans[i] = count;
}
// **** return answer ****
return ans;
}
We start by performing a sanity check. They are useful to pick up simple cases and avoid having to deal with them after initialization.
We declare an integer array that holds all the values in the range [0 : n].
We then enter a loop to generate each entry in the array.
The second loop is used to count bits with value 1 in the current number.
After the second loop the count is set in the current entry in the `ans` array.
When done, the `ans` array is returned.
Not the best time but accepted by LeetCode.
The time complexity is O(n * log(n)) due to the fact that we have to process n entries and for each entry we need to traverse the integer value checking each bit.
**** Tabulation Recipe **** 1. Visualize the problem as a table 2. Size the table based on the inputs 3. Initialize the table with some values 4. Seed the trivial answer into the table 5. Iterate through the table 6. Fill further positions based on the current position
Since we are using tabulation, we should follow the recipe. We need to visualize the problem as a table. In this case this is simple because each number will have associated entry in a table with the count of 1-bits.
The size of the resulting table is suggested by the requirements as to what we need to return from the function.
Initialization of the table seems reasonable. We just set all values to 0.
We could seed the trivial answer in the table implicitly because the first entry will be set to 0 which is done automatically by Java when we declare the table.
The problem starts when we need to figure how we are going to iterate through the table. This is the tricky aspect of the problem at hand.
binary decimal # of 1-bits comments ------+--------+-----------+--------- 0 0 0 0 1 1 odd 1 0 + 1 = 1 10 2 even 1 1 11 3 odd 2 1 + 1 = 2 100 4 even 1 1 101 5 odd 2 1 + 1 = 2 110 6 even 2 2 111 7 odd 3 2 + 1 = 3 1000 8 even 1 1 n / 2; when n is ODD the LSB is 1 and will be lost (result will have 1 less bit set) n / 2; when n is EVEN the LSB is 0 and will NOT change the # of bits set (result will have same bits set))
To figure what to do with the table we need to generate a table with values and see if we can determine a pattern.
The table that we are proposing contains multiple columns.
The first column contains the values expressed in binary. The second column contains the same value expressed in decimal. Note that it also indicates if the value is odd or even. This label will have some significance shortly.
The third column indicates the number of bits that are set to 1 in each value. We can easily check this by looking at the contents of the first column.
Now comes the observation which is key to solving this problem. Let’s take a look at an entry with even entries in the table; for example 8. If you take 8 and divide it by 2 we get 4. We look at entry 4 and see that the number of bits set to one is 1.
We then take 4 and divided by 2 to get 2 as a result. We go to the table and look for the number of bits in that entry and we see that it also holds 1. It seems that we can take the value in entry i / 2 and copy it to entry i. The reason for this is that if you take an even value, the LSB will be 0. When divided by 2 we eliminate the LBS which is 0, so it does not alter the count of bits with value 1.
So what about the odd entries in the table? Let’s take entry 7. We take 7 and divide it by 2 resulting in 3. Entry 3 has a value of 2 bits set to 1. For 7 we need 3 bits set to 1. Note that if the LSB of 7 is divided by 2 we lose the LSB which is set to 1 so we need to add it back.
With this in mind let’s now take a look at the code for the tabulation implementation.
/**
* Given an integer n, return an array ans of length n + 1 such that
* for each i (0 <= i <= n),
* ans[i] is the number of 1's in the binary representation of i.
*
* Using tabulation.
*
* Time: O(n) - Space: O(n)
*
* Runtime: 1 ms, faster than 99.93% of Java online submissions.
* Memory Usage: 43.4 MB, less than 37.18% of Java online submissions.
*/
static int[] countBits(int n) {
// **** sanity checks ****
if (n == 0) return new int[0];
// **** initialization ****
int[] table = new int[n + 1];
// **** populate table ****
for (int i = 1; i <= n; i++)
table[i] = table[i >> 1] + (i & 1);
// **** return table ****
return table;
}
We start by performing a sanity check.
The table is initializes as before.
We then enter a loop in which we populate the table by looking at the entry with half the value. If the value is even we just copy the previous value. If the value is odd we copy the previous value but we add 1 to compensate with the LSB situation.
When done we return the table as an answer.
This implementation runs in O(n) time and the test cases are executed in less time.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John