Reformat Phone Number

🏠 ⬅️ ➡️

You are given a phone number as a string number. number consists of digits, spaces ' ', and/or dashes '-'.

You would like to reformat the phone number in a certain manner. Firstly, remove all spaces and dashes. Then, group the digits from left to right into blocks of length 3 until there are 4 or fewer digits. The final digits are then grouped as follows:

  • 2 digits: A single block of length 2.
  • 3 digits: A single block of length 3.
  • 4 digits: Two blocks of length 2 each.

The blocks are then joined by dashes. Notice that the reformatting process should never produce any blocks of length 1 and produce at most two blocks of length 2.

Return the phone number after formatting.

Example 1:

Input: number = "1-23-45 6 " Output: "123-456 " Explanation: The digits are "123456 ". Step 1: There are more than 4 digits, so group the next 3 digits. The 1st block is "123 ". Step 2: There are 3 digits remaining, so put them in a single block of length 3. The 2nd block is "456 ". Joining the blocks gives "123-456 ".

Example 2:

Input: number = "123 4-567 " Output: "123-45-67 " Explanation: The digits are "1234567 ". Step 1: There are more than 4 digits, so group the next 3 digits. The 1st block is "123 ". Step 2: There are 4 digits left, so split them into two blocks of length 2. The blocks are "45 " and "67 ". Joining the blocks gives "123-45-67 ".

Example 3:

Input: number = "123 4-5678 " Output: "123-456-78 " Explanation: The digits are "12345678 ". Step 1: The 1st block is "123 ". Step 2: The 2nd block is "456 ". Step 3: There are 2 digits left, so put them in a single block of length 2. The 3rd block is "78 ". Joining the blocks gives "123-456-78 ".

Constraints:

  • 2 <= number.length <= 100
  • number consists of digits and the characters '-' and ' '.
  • There are at least two digits in number.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main

! This program solves the following problem:
!
! Given a phone number as a string `number`, you would like to reformat the phone number in a certain manner.
! Firstly, remove all spaces and dashes. Then, group the digits from left to right into blocks of length 3 until there are 4 or fewer digits.
! The final digits are then grouped as follows:
!
! * 2 digits: A single block of length 2.
! * 3 digits: A single block of length 3.
! * 4 digits: Two blocks of length 2 each.
!
! The blocks are then joined by dashes. Notice that the reformatting process should never produce any blocks of length 1 and produce at most two blocks of length 2.
!
! Return the phone number after formatting.
!
! Example 1:
! Input: number = "1-23-45 6 "
! Output: "123-456 "
! Explanation: The digits are "123456 ".
! Step 1: There are more than 4 digits, so group the next 3 digits. The 1st block is "123 ".
! Step 2: There are 3 digits remaining, so put them in a single block of length 3. The 2nd block is "456 ".
! Joining the blocks gives "123-456 ".
!
! Example 2:
! Input: number = "123 4-567 "
! Output: "123-45-67 "
! Explanation: The digits are "1234567 ".
! Step 1: There are more than 4 digits, so group the next 3 digits. The 1st block is "123 ".
! Step 2: There are 4 digits left, so split them into two blocks of length 2. The blocks are "45 " and "67 ".
! Joining the blocks gives "123-45-67 ".
!
! Example 3:
! Input: number = "123 4-5678 "
! Output: "123-456-78 "
! Explanation: The digits are "12345678 ".
! Step 1: The 1st block is "123 ".
! Step 2: The 2nd block is "456 ".
! Step 3: There are 2 digits left, so put them in a single block of length 2. The 3rd block is "78 ".
! Joining the blocks gives "123-456-78 ".
!
! Constraints:
!
!     2 <= number.length <= 100
!     number consists of digits and the characters '-' and ' '.
!     There are at least two digits in number.

implicit none

character(len=:), allocatable :: number
integer :: i, j, k, l, m

number = "1-23-45 6 "
call format_phone_number(number)
write (*,*) trim(number) ! "123-456 "

number = "123 4-567 "
call format_phone_number(number)
write (*,*) trim(number) ! "123-45-67 "

number = "123 4-5678 "
call format_phone_number(number)
write (*,*) trim(number) ! "123-456-78 "

contains

subroutine format_phone_number(number)
    implicit none
    character(len=*), intent(inout) :: number
    integer :: n, i, j, k, l, m
    logical :: has_dash

    ! Remove all spaces and dashes
    do i = 1, len(number)
        if (number(i:i) == ' ' .or. number(i:i) == '-') then
            number(i:i) = ''
        end if
    end do

    ! Group the digits into blocks of length 3 until there are 4 or fewer digits
    n = len(number)
    k = 0
    do while (n > 0)
        if (k == 0) then
            k = min(3, n)
❌ Compiled
❌ Executed
❌ Correct 
! This code reformats a phone number according to the given specifications.

program phone_number_reformatter
implicit none
character(len=100) :: number
character(len=100) :: reformatted_number
integer :: i, j, k, l

! Read the phone number from the input.
read(*,*) number

! Remove all spaces and dashes from the phone number.
number = adjustl(number)
number = trim(number)

! Initialize the reformatted phone number to an empty string.
reformatted_number = ""

! Loop through the phone number and group the digits into blocks of length 3.
i = 1
do while (i <= len(number))
    ! Check if there are 4 or fewer digits left.
    if (len(number) - i + 1 <= 4) then
        ! There are 4 or fewer digits left, so group the remaining digits.
        reformatted_number = trim(reformatted_number) // number(i:len(number))
        exit
    end if

    ! Group the next 3 digits.
    j = i + 3
    if (j > len(number)) then
        j = len(number)
    end if
    reformatted_number = trim(reformatted_number) // number(i:j)
    i = j + 1
end do

! Check if there are 2 or 3 digits left.
if (len(reformatted_number) == 2) then
    ! There are 2 digits left, so group them as a single block of length 2.
    reformatted_number = trim(reformatted_number) // "-" // number(len(reformatted_number)+1:len(reformatted_number)+2)
else if (len(reformatted_number) == 3) then
    ! There are 3 digits left, so group them as a single block of length 3.
    reformatted_number = trim(reformatted_number) // "-" // number(len(reformatted_number)+1:len(reformatted_number)+3)
else if (len(reformatted_number) == 4) then
    ! There are 4 digits left, so group them into two blocks of length 2 each.
    reformatted_number = trim(reformatted_number) // "-" // number(len(reformatted_number)+1:len(reformatted_number)+2) // "-" // number(len(reformatted_number)+3:len(reformatted_number)+4)
end if

! Print the reformatted phone number to stdout.
write(*,*) trim(reformatted_number)

end program phone_number_reformatter
🌐 Data from online sources 
def min_subarray(nums, p):
    n = len(nums)
    need, cur, res = 0, 0, n
    last_seen = {}

    for num in nums:
        need = (need + num) % p

    if need == 0:
        return 0

    last_seen[cur] = -1
    for i, num in enumerate(nums):
        cur = (cur + num) % p
        last_seen[cur] = i
        want = (cur - need + p) % p
        if want in last_seen:
            res = min(res, i - last_seen[want])

    return res if res != n else -1

The algorithm starts by calculating the sum modulo p of the entire array (called "need"). If the sum is already divisible by p (i.e., need is 0), it returns 0 as no elements need to be removed.

Next, we define an unordered_map (in C++), a HashMap (in Java), a dictionary (in Python), or a Map (in JavaScript) called "last_seen" which keeps track of the last_seen index where each "cur" value appears. "cur" represents the current accumulated sum modulo p.

While iterating through the array, we calculate the "cur" value and put it into the last_seen data structure with the corresponding index i as the value. We also calculate the "want" value, which is the value we need in last_seen to ensure the sum of the remaining elements is divisible by p. If "want" is in last_seen, we update the minimum result length with the difference between the current index and the index where the "want" value was last seen in last_seen.

Finally, if the result length is still equal to the length of the array, it means it is impossible to get a subarray whose sum is divisible by p, so we return -1; otherwise, we return the result length.

🌐 Data from online sources 
#include <vector>
#include <unordered_map>
using namespace std;

int minSubarray(vector<int>& nums, int p) {
    int n = nums.size(), need = 0, cur = 0, res = n;
    for (int num : nums) need = (need + num) % p;
    if (need == 0) return 0;
    unordered_map<int, int> last_seen;
    last_seen[cur] = -1;
    for (int i = 0; i < n; ++i) {
        cur = (cur + nums[i]) % p;
        last_seen[cur] = i;
        int want = (cur - need + p) % p;
        if (last_seen.count(want)) {
            res = min(res, i-last_seen[want]);
        }
    }
    return res == n ? -1 : res;
}

The algorithm starts by calculating the sum modulo p of the entire array (called "need"). If the sum is already divisible by p (i.e., need is 0), it returns 0 as no elements need to be removed.

Next, we define an unordered_map (in C++), a HashMap (in Java), a dictionary (in Python), or a Map (in JavaScript) called "last_seen" which keeps track of the last_seen index where each "cur" value appears. "cur" represents the current accumulated sum modulo p.

While iterating through the array, we calculate the "cur" value and put it into the last_seen data structure with the corresponding index i as the value. We also calculate the "want" value, which is the value we need in last_seen to ensure the sum of the remaining elements is divisible by p. If "want" is in last_seen, we update the minimum result length with the difference between the current index and the index where the "want" value was last seen in last_seen.

Finally, if the result length is still equal to the length of the array, it means it is impossible to get a subarray whose sum is divisible by p, so we return -1; otherwise, we return the result length.