Unreachable leaves by frogs
Given N frogs, M leaves, and strength K for each frog. The task is to find the number of leaves that cannot be visited by any of the frogs when all frogs have reached the other end of the pond where each frog has the strength to jump exactly K leaves.
Examples:
Input: N = 3, M = 4, frogs[] = {3, 2, 4}
Output: 1
Explanation: Leaf 1 will not be visited by any frog.Input: N = 3, M = 6, frogs[] = {1, 3, 5}
Output: 0
Explanation: The first frog will visit all the leaves so no leaf is left unvisited.
Approach: This can be solved with the following idea:
We can imitate each frog’s movement and label the leaves they visit in order to determine the number of unvisited leaves. By deducting the number of visited leaves from the total number of leaves, we can then calculate the number of unvisited leaves. We may use a set to keep track of the leaves that each of the frogs visited in order to make the simulation effective.
Steps involved in the implementation of the code:
- Create an empty set to record the leaves that have been visited.
- Simulate the movement of each frog on the list, then add its visited leaves to the collection of visited leaves.
- Provide the total number of leaves minus the size of the set of visited leaves, which is equal to the number of unvisited leaves.
C++
#include <algorithm> #include <iostream> #include <vector> using namespace std; int unvisitedLeaves( int N, int leaves, vector< int >& frogs) { int max_jump = *max_element(frogs.begin(), frogs.end()); vector< int > visited(leaves, 0); for ( int frog : frogs) { for ( int i = frog - 1; i < leaves; i += frog) { visited[i] = 1; } } return count(visited.begin(), visited.end(), 0); } int main() { int N = 3; int leaves = 4; vector< int > frogs = { 3, 2, 4 }; // Function call cout << unvisitedLeaves(N, leaves, frogs) << endl; return 0; } // This code is contributed by shivamgupta0987654321 |
Java
import java.util.*; class Main { public static int unvisitedLeaves( int N, int leaves, ArrayList<Integer> frogs) { // Find the maximum jump among all frogs int max_jump = Collections.max(frogs); // Create a list to track visited leaves ArrayList<Integer> visited = new ArrayList<>(Collections.nCopies(leaves, 0 )); // Mark leaves as visited based on frog jumps for ( int frog : frogs) { for ( int i = frog - 1 ; i < leaves; i += frog) { visited.set(i, 1 ); } } // Count the number of unvisited leaves return Collections.frequency(visited, 0 ); } // Driver code public static void main(String[] args) { int N = 3 ; // Number of frogs int leaves = 4 ; // Number of leaves ArrayList<Integer> frogs = new ArrayList<>(Arrays.asList( 3 , 2 , 4 )); // Frog jump lengths // Function call System.out.println(unvisitedLeaves(N, leaves, frogs)); } } // This code is contributed by akshitaguprzj3 |
Python3
# Python3 Implementation # Function to find number of unvisited # links def unvisitedLeaves(N, leaves, frogs): max_jump = max (frogs) visited = [ 0 ] * leaves for frog in frogs: for i in range (frog - 1 , leaves, frog): visited[i] = 1 return visited.count( 0 ) # Driver code if __name__ = = '__main__' : N = 3 leaves = 4 frogs = [ 3 , 2 , 4 ] # Function call print (unvisitedLeaves(N, leaves, frogs)) |
C#
using System; using System.Collections.Generic; using System.Linq; class GFG { public static int UnvisitedLeaves( int N, int leaves, List< int > frogs) { // Create a list to track visited leaves List< int > visited = Enumerable.Repeat(0, leaves).ToList(); // Mark leaves as visited based on frog jumps foreach ( int frog in frogs) { for ( int i = frog - 1; i < leaves; i += frog) { visited[i] = 1; } } // Count the number of unvisited leaves return visited.Count(v => v == 0); } public static void Main( string [] args) { int N = 3; // Number of frogs int leaves = 4; // Number of leaves List< int > frogs = new List< int > { 3, 2, 4 }; // Frog jump lengths // Function call Console.WriteLine(UnvisitedLeaves(N, leaves, frogs)); } } |
Javascript
function unvisitedLeaves(N, leaves, frogs) { const max_jump = Math.max(...frogs); const visited = new Array(leaves).fill(0); // Nikunj Sonigara for (const frog of frogs) { for (let i = frog - 1; i < leaves; i += frog) { visited[i] = 1; } } return visited.filter((value) => value === 0).length; } const N = 3; const leaves = 4; const frogs = [3, 2, 4]; // Function call console.log(unvisitedLeaves(N, leaves, frogs)); |
1
Time Complexity: O(N * L)
Auxiliary space: O(L)