Add to Array-Form of Integer

🏠 ⬅️ ➡️

The array-form of an integer num is an array representing its digits in left to right order.

  • For example, for num = 1321, the array form is [1,3,2,1].

Given num, the array-form of an integer, and an integer k, return the array-form of the integer num + k.

Example 1:

Input: num = [1,2,0,0], k = 34 Output: [1,2,3,4] Explanation: 1200 + 34 = 1234

Example 2:

Input: num = [2,7,4], k = 181 Output: [4,5,5] Explanation: 274 + 181 = 455

Example 3:

Input: num = [2,1,5], k = 806 Output: [1,0,2,1] Explanation: 215 + 806 = 1021

Constraints:

  • 1 <= num.length <= 104
  • 0 <= num[i] <= 9
  • num does not contain any leading zeros except for the zero itself.
  • 1 <= k <= 104
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer :: num(4), k
    integer :: i

    ! Example 1
    num = [1, 2, 0, 0]
    k = 34
    call print_array_form(num)
    write (*,*) " + ", k, " = "
    call add_to_array_form(num, k)
    call print_array_form(num)
    write (*,*) ""

    ! Example 2
    num = [2, 7, 4]
    k = 181
    call print_array_form(num)
    write (*,*) " + ", k, " = "
    call add_to_array_form(num, k)
    call print_array_form(num)
    write (*,*) ""

    ! Example 3
    num = [2, 1, 5]
    k = 806
    call print_array_form(num)
    write (*,*) " + ", k, " = "
    call add_to_array_form(num, k)
    call print_array_form(num)
    write (*,*) ""

contains

    subroutine print_array_form(num)
        implicit none
        integer, intent(in) :: num(:)
        integer :: i

        do i = size(num), 1, -1
            write (*,*) num(i), " "
        end do
    end subroutine print_array_form

    subroutine add_to_array_form(num, k)
        implicit none
        integer, intent(inout) :: num(:)
        integer, value :: k
        integer :: carry

        carry = 0
        do i = 1, size(num)
            num(i) = num(i) + carry
            carry = num(i) / 10
            num(i) = mod(num(i), 10)
        end do
        if (carry > 0) then
            allocate(num(size(num)+1))
            num(1:size(num)-1) = 0
            num(size(num)) = carry
        end if
    end subroutine add_to_array_form

end program main
❌ Compiled
❌ Executed
❌ Correct 
module AddToArrayForm
    implicit none
    private
    public :: addToArrayForm
contains
    function addToArrayForm(num, k) result(result)
        integer, intent(in) :: num(:)
        integer, intent(in) :: k
        integer :: result(size(num))

        integer :: carry, i

        carry = k
        do i = 1, size(num)
            result(i) = (num(i) + carry) mod 10
            carry = (num(i) + carry) / 10
        end do

        if (carry > 0) then
            allocate(result(size(num) + 1))
            result(1:size(num)) = num
            result(size(num) + 1) = carry
        end if
    end function addToArrayForm
end module AddToArrayForm

program test_addToArrayForm
    use AddToArrayForm
    implicit none
    integer, parameter :: num = [1, 3, 2, 1]
    integer, parameter :: k = 34
    integer :: result(size(num))

    result = addToArrayForm(num, k)

    write (*,*) "Result: ", result
end program test_addToArrayForm
🌐 Data from online sources 
from collections import defaultdict

def largestComponentSize(nums):
    def primes(n):
        for i in range(2, int(n**0.5) + 1):
            if n % i == 0:
                return i
        return n

    def dfs(node, visited, graph):
        if node in visited:
            return 0
        visited.add(node)
        size = 1
        for neighbor in graph[node]:
            size += dfs(neighbor, visited, graph)
        return size

    graph = defaultdict(set)
    visited = set()

    for num in nums:
        prime = primes(num)
        graph[prime].add(num)
        if num != prime:
            graph[num].add(prime)

    count = 0
    for num in nums:
        count = max(count, dfs(num, visited, graph))

    return count

The algorithm uses the following steps:

  1. For each number in nums, find the smallest prime divisor, which is the prime number that divides the current number.
  2. Construct a graph where the nodes are numbers, and the edges are between each number and its smallest prime divisor.
  3. Perform a depth-first search (DFS) on the graph for each number in nums, counting the size of connected components and keeping track of visited nodes.
  4. Return the size of the largest connected component in the graph.

This algorithm starts by mapping each number to its smallest prime divisor, and then building a graph to model the relationships between the numbers and the divisors. The DFS traversal helps to find connected components, and the largest connected component is returned. The time complexity of this algorithm is O(N√W), where N is the size of the nums array, and W is the maximum number in it.

🌐 Data from online sources 
#include<vector>
#include<unordered_set>
#include<unordered_map>

using namespace std;

int primes(int n) {
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) return i;
    }
    return n;
}

int largestComponentSize(vector<int>& nums) {
    int count = 0;
    unordered_map<int, unordered_set<int>> graph;
    unordered_set<int> visited;
    for (int num : nums) {
        int prime = primes(num);
        graph[prime].insert(num);
        if (num != prime) graph[num].insert(prime);
    }

    function<int(int)> dfs = [&](int node) {
        if (!visited.insert(node).second) return 0;
        int res = 1;
        for (int neighbor : graph[node]) {
            res += dfs(neighbor);
        }
        return res;
    };

    for (int num : nums) {
        count = max(count, dfs(num));
    }
    return count;
}

The algorithm uses the following steps:

  1. For each number in nums, find the smallest prime divisor, which is the prime number that divides the current number.
  2. Construct a graph where the nodes are numbers, and the edges are between each number and its smallest prime divisor.
  3. Perform a depth-first search (DFS) on the graph for each number in nums, counting the size of connected components and keeping track of visited nodes.
  4. Return the size of the largest connected component in the graph.

This algorithm starts by mapping each number to its smallest prime divisor, and then building a graph to model the relationships between the numbers and the divisors. The DFS traversal helps to find connected components, and the largest connected component is returned. The time complexity of this algorithm is O(N√W), where N is the size of the nums array, and W is the maximum number in it.