Power of Three

Today seems that it is turning into a beautiful summer Sunday in the Twin Cities of Minneapolis and St. Paul. The high temperature in the suburb where I live is forecasted to get up to 77 F and the day will be sunny. It is almost a carbon copy of yesterday.

My wife and I live in a suburb of the Twin Cities. This area has not been affected by protests from BLM (Black Lives Matter). As you know the last set of riots and lootings started in the city of Minneapolis when a black person dies while in police custody. At the time the mayor of Minneapolis and governor failed to provide basic security and law enforcement and for no reason, many businesses were looted and burned. Those were the facts a few months ago.

Last week a black person, also with a long police record, killed some other individual. When the police arrived, the black person committed suicide. Social media and news falsely stated that the black person was killed by police. The news tried to correct the misinformation, but a group of BLM protesters gathered in Nicollet mall (a main street in Minneapolis) which is full of high rises with offices, apartment buildings, retails stores and restaurants. Looting started but the mayor of the city and the governor of the state dispatched local police, State Troopers and the National Guard. Property damage was minimized and contained. The move by authorities prevented things to get out of hand.

This morning I read that in some city in Oregon, every night for ninety four consecutive days, BLM has been allowed to gather and commit crimes. Not sure what elected officials wish to prove. In my humble opinion residents should show their response in the next set of elections and get rid of politicians that are not capable to provide basic service to their constituents like basic safety.

I also read an article about how people have been committing election fraud. The person describes how he and other people he knows committed the crimes. This crime which destroys one of the basic pillars of democracy is very simple to commit because of:

Voter ID is not required
Voters do not need to be registered
Voters can cast their vote months before election day

Very few places in the world allow the practices we have in the USA which provide a green light for people who wish to commit vote fraud. India which is almost five times larger as far as population uses a voter ID. It is amazing the points made by politicians (mostly democrats) against using a voter ID card. An average twelve year old understands that such mechanism is needed and the arguments against it do not make sense. By the way, the person that describes how he has committed voter fraud dozens of times is a democrat.

I do not like politics. My wife and I are registered voters, which on election days go to the polls and cast our votes. My parents taught my siblings and me that there are three subjects you should not discuss: politics, money and sex. If you read the news or have accounts on social media, the three main topics are: politics, money and sex. Hopefully we Americans will start realizing that we do not live alone in the world. We are surrounded by good friendly people (i.e., Canada, Israel, and the United Kingdom, among others) and bad ones (i.e., China, Iran, among others) that want to cause harm, not only to us but to the entire world. Let’s pay attention to the real news (which seem fewer and far apart) and make educated decisions. Writing and republishing snippets in social media is not enough. We need to improve in the way we treat our families, our coworkers, our neighbors, and the way we work and study. Let’s stop making excuses and blaming politicians for what we fail to do. Remember that politicians are elected officials and we can just not vote for them. If we do not like products being manufactured in China, do not buy them. If we do not like the services of a company, do not use them. Such actions are simple and can make a huge change in America.

A few weeks ago, our son gave us an ice cream recipe. It only contains five ingredients. The only possible drawback is that you need a stand mixer with an ice cream bowl attachment. It just happens that we have both. We briefly looked for the attachment but could not find it. We believe we know where to look in the garage, but with the excuse that it is hot during summer, we decided to adapt and make it simpler. We use the standard bowl and whisk instead of the one specialized for making ice cream. We have also experimented with the ingredients by adding new ones, changing some, and modifying amounts. Sometimes the results are not as expected, while others are generating a better product. The approach is similar to how people working on different aspects of software development should proceed at work. If something is more difficult than it should be, induce a change. With practice and time (experience) you will be happier with the software development process and the results you deliver to your customers.

OK, that was a lot to say. Now let’s get to the core subject for this post.

I searched in the LeetCode site using the term “recursion” and selected problem 326 Power of Three. As the name for the problem suggests, we have to determine is an integer is a power (not just a multiple) of 3. The LeetCode web site suggests if one could get it done without using a loop or recursion. If you are interested please visit the site, read the requirements, and dive into writing the code for the required function.

    public boolean isPowerOfThree(int n) {
        
    }

You can go directly to the LeetCode web site and use it to develop your solution. The advantage is that you do not have to write your own test scaffolding. I, like most (never generalize) people I know, use for work their own setup which includes the OS and development tools. For this problem I will use the Java programming language, the VSCode IDE both running on a Windows 10 machine. At home I have about a dozen computers. Of those, every morning, I power up two Windows and one Linux system. And yes, I have virtual machine software installed on different machines, but I like to use the real thing.

main <<< largestPowerOf3: 1162261467
27
main <<< n: 27
main <<< true
main <<< true


main <<< largestPowerOf3: 1162261467
0
main <<< n: 0
main <<< false
main <<< false


main <<< largestPowerOf3: 1162261467
9
main <<< n: 9
main <<< true
main <<< true


main <<< largestPowerOf3: 1162261467
45
main <<< n: 45
main <<< false
main <<< false


main <<< largestPowerOf3: 1162261467
1
main <<< n: 1
main <<< true
main <<< true


main <<< largestPowerOf3: 1162261467
64
main <<< n: 64
main <<< false
main <<< false


main <<< largestPowerOf3: 1162261467
-3
main <<< n: -3
main <<< false
main <<< false

The test scaffolding that I wrote seems to display too many things. What we need to do is get an integer i.e., 27 and return true because 3 ^ 3 = 27. The first three or so examples are the ones provided by LeetCode. The others came from me or LeetCode when a version of the code I was submitting failed. We will see more of what is happening when we discuss the test scaffolding.

    /**
     * Test scaffolding.
     */
    public static void main(String[] args) {
        
        // **** generate largest power of 3 ****
        largestPowerOf3 = findLargestPower(3);

        // **** ****
        System.out.println("main <<< largestPowerOf3: " + largestPowerOf3);

        // **** open scanner ****
        Scanner sc = new Scanner(System.in);

        // *** read integer ***
        int n = sc.nextInt();

        // ???? ????
        System.out.println("main <<< n: " + n);

        // **** close scanner ****
        sc.close();

        // **** check and display if integer is power of three ****
        System.out.println("main <<< " + isPowerOfThree(n));

        // **** check and display if integer is power of three ****
        System.out.println("main <<< " + isPowerOf3(n));
    }

We start by finding the largest power of integer 3. At this point this is not required to solve the problem at hand. That said, you can verify that the returned value is the largest integer value that an integer variable can hold in Java. It is 3 ^ 19 == 1162261467.

We open the scanner, read and display the integer value, and close the scanner. I was going to replace this set of instructions with a loop in the range [-7 : 17] but ended up just prompting for an individual value.

We then generate the result using two different approaches and display them to verify and compare. If all is well, they will both produce the same correct value:  true or false.

    /**
     * Determine if 'n'' is a power of three.
     */
    static boolean isPowerOfThree(int n) {
        
        // **** not a power of three ****
        if (n < 1)
            return false;

        // **** ****
        while ((n % 3) == 0) {
            n /= 3;
        }

        // **** ****
        return (n == 1) ? true : false;
    }

This is the function we need to put in our solution. We start by checking if the integer is negative. The core is implemented in the loop. We get the reminder and if there is none, we divide n by 3 and try again. Sooner or later we will exit the loop. If we got down to n == 1 we were provided with a power of 3; otherwise we return false. This code was accepted by LeetCode.

    /**
     * Find the value of the largest power of n.
     * The returned value could be used as a constant.
     * In that case this function would not be used.
     * 
     */
    static int findLargestPower(int n) {

        // **** initialization ****
        int r = 1;

        // **** loop until we get an overflow exception ****
        for (int i = 1; true; i++) {

            // **** ****
            try {
                r = Math.multiplyExact(r, n);
            } catch (ArithmeticException e) {

                // ???? ????
                // System.out.println("findLargestPower <<< EXCEPTION e: " + e);

                // **** return the larget power of n ****
                return r;
            }

            // ???? ????
            // System.out.println("findLargestPower <<< i: " + i + " r: " + r);
        }
    }

This code has nothing to do with our base solution. As we will see shortly, the value returned by this function can be used to obtain the result in O(1) time, which is better than O(log n). In this function we start with number 1 and multiply it by 3 in each pass of the loop. If we just use r *=3 the operation will overflow but will not throw an exception. We use the multiplyExact() method from the Math library. It will throw an overflow exception. This is used to return the proper value which in our case is displayed to the screen.

We could define a variable or a constant with this value and use it when calling a function that makes use of it.

    // **** for easy access after computing ****
    static int largestPowerOf3              = 0;

    // **** as a constant ****
    static final int LARGEST_POWER_OF_3    = 1162261467;

That is exactly what we did. We declared a variable and computed outside the function or declare it as a constant which we computed beforehand.

    /**
     * Determine if 'n'' is a power of three.
     * Runs in O(1) time.
     */
    static boolean isPowerOf3(int n) {
    
        // **** ****
        if (n < 1)
            return false;
        // else
        //    return (n != 0) && (LARGEST_POWER_OF_3 % n == 0);
        
        // **** ****
        return (LARGEST_POWER_OF_3 % n == 0);
    }

In this function we check if the integer is 0 or negative and return false. We then use a constant which we named LARGEST_POWER_OF_3 and a single mod operation. If the resulting value is 0 we have a power of 3; otherwise we do not. This function runs in O(1) time.

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, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address:  john.canessa@gmail.com. I will reply as soon as possible.

Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!

One last thing, many thanks to all 1739 subscribers to this blog!!!

Keep safe during the COVID-19 pandemic and help restart the world economy.

John

Twitter:  @john_canessa

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.