Powerfull Integer Problem Solved: Uncover the Most Efficient Java Algorithm

 

Problem

Problem_Link

Problem Solving Approach

1. Traverse through all the numbers in the intervals and store their frequencies in a HashMap.
2. Sort the hashmap based on the keys.→in worst case, O(n log n)
3. Find the maximum powerful integer by iterating through the sorted hashmap, which occurs at least k times.

Time Complexity: O(n log n), Space Complexity: O(n)

https://github.com/eunhanlee/powerfullInteger/blob/master/read%20me.md

import java.util.*;
class Solution {

    /**
     * This method takes in the number of intervals n, the 2D integer array of intervals interval, and the minimum number of occurrences k for a number to be considered powerful.
     * It returns the powerful integer which occurs at least k times. If multiple integers have at least k occurrences, the maximum integer out of all those elements is returned.
     * If no integer occurs at least k times, -1 is returned.
     *
     * @param n         the number of intervals
     * @param interval  the 2D integer array of intervals where interval[i] = [start, end]
     * @param k         the minimum number of occurrences for a number to be considered powerful
     * @return the powerful integer which occurs at least k times, or -1 if no integer occurs at least k times
     */
    public static int powerfullInteger(int n, int[][] interval, int k) {
        // A hashmap to store the frequency of each number
        Map<Integer, Integer> map = new HashMap<>();
        // The maximum powerful integer that occurs at least k times, if there is no, return -1
        int maxPowerful = -1;

        // Loop through each interval and update the frequency of each number in the hashmap
        for (int i = 0; i < n; i++) {
            for (int j = interval[i][0]; j <= interval[i][1]; j++) {
                map.put(j, map.getOrDefault(j, 0) + 1);
            }
        }

        // Sort the hashmap by key
        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
        list.sort(Map.Entry.comparingByKey());

        // find the maximum powerful integer
        for (Map.Entry<Integer, Integer> val : list) {
            if (val.getValue() >= k) {
                maxPowerful = val.getKey();
            }
        }

        return maxPowerful;
    }
}

find number Problem Solved: Uncover the Most Efficient Java Algorithm

Problem

Problem_Link

Problem Solving Approach

• Odd digit numbers have a pattern

  1	3	5	7	9
  11	13	15	17	19
  31	33	35	37	39
  51	53	55	57	59
  71	73	75	77	79
  91	93	95	97	99
  101	103	105	107	109

• As seen above, the pattern repeats every 5 numbers.

• Therefore, we can know the position of each digit by dividing N by 5.

• If we know the position of each digit, we can find out what number will be in that position (1, 3, 5, 7, 9)

• Let's take the 13th odd digit number as an example

  • The rightmost digit (ones place) in 13 is the 3rd.

  • According to the odd digit pattern, the third number is 5.

  • The second rightmost digit (tens place) in 13 is the 2nd.

  • According to the odd digit pattern, the second number is 3.

  • In conclusion, the 13th odd digit number is 35.

• Let's take the 27th odd digit number as an example

  • The rightmost digit (ones place) in 27 is the (27%5) 2nd.

  • According to the odd digit pattern, the second number is 3.

  • Excluding the calculated digits from 27, we get 27-27%5 = 27/5=5.

  • The second rightmost digit (tens place) is the (5%5) 5th.

  • According to the odd digit pattern, the fifth number is 9.

  • In conclusion, the 27th odd digit number is 93.

• There is something slightly incorrect with the above pattern. For example, 5%5 is 0. However, we want the pattern to follow the table above.

  - n % 5 = 0 //5th number = 9
  - n % 5 = 1 //1th number = 1
  - n % 5 = 2 //2th number = 3
  - n % 5 = 3 //3th number = 5
  - n % 5 = 4 //4th number = 7

  To fix this, we subtract 1 from n.

  - n-1 % 5 = 0 //1th number = 1
  - n-1 % 5 = 1 //2th number = 3
  - n-1 % 5 = 2 //3th number = 5
  - n-1 % 5 = 3 //4th number = 7
  - n-1 % 5 = 4 //5th number = 9

• Lastly, when we get 0, 1, 2, 3, 4, the actual numbers we want are 1, 3, 5, 7, 9. To optimize this, we multiply by 2 and add 1.

  0*2+1=1
  2*2+1=3
  3*2+1=5
  4*2+1=7
  5*2+1=9

Time O(log n), Space O(1)

https://github.com/eunhanlee/findNumber_Solution_gfg.git

class Solution
{
    /**
     * Finds the Nth number containing only odd digits.
     *
     * @param N The position of the desired number.
     * @return The Nth number containing only odd digits.
     */
    public long findNumber(long N)
    {
        // The variable to store the final result
        long result = 0;
        // The variable to represent the digit position (1, 10, 100, ...)
        long position = 1;

        // Continue until N is greater than 0
        while (N > 0)
        {
            // Calculate the odd digit by subtracting 1 from N and dividing by 5
            long oddDigit = ((N - 1) % 5) * 2 + 1;
            // Subtract 1 from N and divide by 5 to prepare for the next digit calculation
            N = (N - 1) / 5;
            // Add the odd digit multiplied by the current position to the result
            result += oddDigit * position;
            // Move to the next digit position
            position *= 10;
        }

        // Return the Nth number containing only odd digits
        return result;
    }
}

Explanation

• The given integer N is repeatedly divided by 5 during the computation process, which reduces its value. In this process, odd-digit numbers are generated. The loop continues as long as N is greater than 0.

• With each iteration, N is updated to (N - 1) / 5. This process reduces N by more than half, causing N to decrease significantly with each iteration. Since N is almost halved with each iteration, the time complexity can be considered as O(log N).

How to Find Substrings in a String

 

Definition of substring

A sequence of consecutive characters within a larger string.

In other words, it is a smaller string that is written without changing the order of the characters selected from the original string or skipping any characters in the middle.

Example of substrings

Substrings of "abc": "", "a", "b", "c", "ab", "bc", "abc"

In mathematics, the empty string ("") is also considered a substring.

However, in programming problems, whitespace characters are usually not considered as substrings.

How to find substrings

Example

public static int countSubstring(String str) {
    int n = str.length();
    return n*(n+1)/2;
}