Kids With the Greatest Number of Candies

🏠 ⬅️ ➡️

There are n kids with candies. You are given an integer array candies, where each candies[i] represents the number of candies the ith kid has, and an integer extraCandies, denoting the number of extra candies that you have.

Return a boolean array result of length n, where result[i] is true if, after giving the ith kid all the extraCandies, they will have the greatest number of candies among all the kids__, or false otherwise.

Note that multiple kids can have the greatest number of candies.

Example 1:

Input: candies = [2,3,5,1,3], extraCandies = 3 Output: [true,true,true,false,true] Explanation: If you give all extraCandies to: - Kid 1, they will have 2 + 3 = 5 candies, which is the greatest among the kids. - Kid 2, they will have 3 + 3 = 6 candies, which is the greatest among the kids. - Kid 3, they will have 5 + 3 = 8 candies, which is the greatest among the kids. - Kid 4, they will have 1 + 3 = 4 candies, which is not the greatest among the kids. - Kid 5, they will have 3 + 3 = 6 candies, which is the greatest among the kids.

Example 2:

Input: candies = [4,2,1,1,2], extraCandies = 1 Output: [true,false,false,false,false] Explanation: There is only 1 extra candy. Kid 1 will always have the greatest number of candies, even if a different kid is given the extra candy.

Example 3:

Input: candies = [12,1,12], extraCandies = 10 Output: [true,false,true]

Constraints:

  • n == candies.length
  • 2 <= n <= 100
  • 1 <= candies[i] <= 100
  • 1 <= extraCandies <= 50
Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
✅ Correct 
program main
    implicit none

    integer, parameter :: n = 5
    integer, dimension(n) :: candies = [2, 3, 5, 1, 3]
    integer :: extraCandies = 3
    logical, dimension(n) :: result

    result = solve(candies, extraCandies)

    write (*, '(L1)') result

contains

    function solve(candies, extraCandies) result(result)
        implicit none
        integer, intent(in) :: candies(:), extraCandies
        logical, dimension(size(candies)) :: result
        integer :: i

        do i = 1, size(candies)
            result(i) = (candies(i) + extraCandies) >= maxval(candies)
        end do
    end function solve
end program main
❌ Compiled
❌ Executed
❌ Correct 
module kids_with_the_greatest_number_of_candies
    implicit none

contains

    function kids_with_the_greatest_number_of_candies(candies, extra_candies) result(result)
        integer, intent(in) :: candies(:)
        integer, intent(in) :: extra_candies
        logical :: result(size(candies))

        ! Declare local variables
        integer :: i, max_candies, current_candies

        ! Initialize the result array
        result = .false.

        ! Find the maximum number of candies
        max_candies = maxval(candies)

        ! Loop through the kids
        do i = 1, size(candies)
            ! Calculate the current number of candies
            current_candies = candies(i) + extra_candies

            ! Check if the current number of candies is greater than the maximum
            if (current_candies >= max_candies) then
                ! Set the result to true
                result(i) = .true.
            end if
        end do

    end function kids_with_the_greatest_number_of_candies

end module kids_with_the_greatest_number_of_candies

program test_kids_with_the_greatest_number_of_candies
    use kids_with_the_greatest_number_of_candies
    implicit none

    ! Declare the variables
    integer, parameter :: n = 5
    integer, parameter :: extra_candies = 3
    integer :: i
    integer :: candies(n) = [2, 3, 5, 1, 3]
    logical :: result(n)

    ! Call the function
    result = kids_with_the_greatest_number_of_candies(candies, extra_candies)

    ! Print the result
    do i = 1, n
        write (*,*) result(i)
    end do

end program test_kids_with_the_greatest_number_of_candies
🌐 Data from online sources 
from collections import defaultdict

def find_ancestors(node, adj_list, visited, ans):
    if visited[node]:
        return
    visited[node] = True
    for ancestor in adj_list[node]:
        ans.append(ancestor)
        find_ancestors(ancestor, adj_list, visited, ans)

def find_ancestors_in_dag(n, edges):
    adj_list = defaultdict(list)
    for edge in edges:
        adj_list[edge[1]].append(edge[0])
    ans = []
    for i in range(n):
        visited = [False] * n
        ancestors = []
        find_ancestors(i, adj_list, visited, ancestors)
        ans.append(sorted(ancestors))
    return ans

The algorithm works by iterating over all the given nodes and finding the ancestors of each node.
  1. Create an adjacency list representation of the graph where the keys are the nodes and the values are lists of their parents.
  2. For each node i in the graph, perform a Depth-First Search using a helper function findAncestors(), to explore all the ancestors by traversing the parent nodes.
  3. During the search, maintain a visited array to prevent infinite loops and avoid visiting already visited nodes.
  4. Append the ancestors of each node to a list and sort it in ascending order.
  5. Return the list of ancestors for all nodes as a nested list.
🌐 Data from online sources 
#include <vector>
#include <algorithm>
using namespace std;

void findAncestors(int node, vector<vector<int>>& adj_list, vector<bool>& visited, vector<int>& ans) {
    if (visited[node]) return;
    visited[node] = true;
    for (int ancestor : adj_list[node]) {
        ans.push_back(ancestor);
        findAncestors(ancestor, adj_list, visited, ans);
    }
}

vector<vector<int>> findAncestorsInDAG(int n, vector<vector<int>>& edges) {
    vector<vector<int>> adj_list(n), ans(n);
    for (vector<int>& edge : edges) {
        adj_list[edge[1]].push_back(edge[0]);
    }
    for (int i = 0; i < n; ++i) {
        vector<bool> visited(n, false);
        findAncestors(i, adj_list, visited, ans[i]);
        sort(ans[i].begin(), ans[i].end());
    }
    return ans;
}

The algorithm works by iterating over all the given nodes and finding the ancestors of each node.
  1. Create an adjacency list representation of the graph where the keys are the nodes and the values are lists of their parents.
  2. For each node i in the graph, perform a Depth-First Search using a helper function findAncestors(), to explore all the ancestors by traversing the parent nodes.
  3. During the search, maintain a visited array to prevent infinite loops and avoid visiting already visited nodes.
  4. Append the ancestors of each node to a list and sort it in ascending order.
  5. Return the list of ancestors for all nodes as a nested list.