Given an array arr[] of size N, an integer K representing the number of leaves in the pond, and the arr[i] indicating the strength of the ith frog’s jump, where 0 <= i < N. The frogs are at one end of the pond and are trying to get to the other end by jumping on the leaves, the task is to count the number of unvisited leaves. After each frog has reached the end while ensuring that every frog jumps with its respective strength.
Examples:
Input: N = 3 , K = 4 , arr [ ] = {3, 2, 4}
Output: 1
Explanation: leaf 2 will be visited by Frog 1, leaf 3 will be visited by frog 0, leaf 4 will be visited by Frog 1, and Frog 2, only leaf 1 remains unvisited.Input: N = 3 , K = 6 , arr [ ] = {1, 3, 5}
Output: 0
Explanation: Frog 0 will visit all the leaves as it jumps a distance of 1, so no leaf remains unvisited.
Naive Approach: We can follow the below idea to solve the problem :
The problem states to find the count of leaves which are unvisited after all the N frogs have crossed the pond. For each frog i with strength strengthi we can iterate over the n leaves starting from 0 where the frog is currently present by jumping the frog from it’s present_leaf to present_leaf + strengthi (the next leaf it will jump on to), which will be the next present_leaf for this ith frog. Thus we can mark the leaves which are visited by this ith frog (the leaf with index that are perfectly divisible by strength of frog i). Similarly after iterating over all the frogs we marked all the leaves that were visited during the crossing of the frogs.
Follow the steps to solve the problem:
- Initialize the visited vector of size leaves+1, and mark them as false
- For each frog, iterate over all the leaves that the frog will visit, and mark that leaf as visited
- Iterate over all the leaves, and increase the answer count by 1 when an unvisited leaf is found
Below is the implementation for the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;int unvisitedLeaves(int N, int leaves, int frogs[]){ // Initialising visited vector for leaves, and // marking them as not vistied initially vector<bool> visited(leaves + 1, false); // Iterating over all frogs for (int i = 0; i < N; ++i) { int strength_i = frogs[i]; // Going through all the leaves ith frog // will visit and mark the leaves as visited for (int j = 0; j <= leaves; j++) { if (j % strength_i == 0) visited[j] = true; } } // Iterating over all the leaves // and if the leaf is not visited, increasing // our count by 1 int unvisitedLeavesCount = 0; for (int i = 0; i <= leaves; ++i) { if (visited[i] == false) { unvisitedLeavesCount++; } } return unvisitedLeavesCount;}// Drivers codeint main(){ int N = 3; int leaves = 6; int frogs[N] = { 3, 6, 2 }; // Function call cout << unvisitedLeaves(N, leaves, frogs) << endl; return 0;} |
Java
import java.util.*;public class GFG { static int unvisitedLeaves(int N, int leaves, int[] frogs) { // Initialising visited array for leaves and // marking them as not visited initially boolean[] visited = new boolean[leaves + 1]; // Iterating over all frogs for (int i = 0; i < N; ++i) { int strength_i = frogs[i]; // Going through all the leaves ith frog // will visit and mark the leaves as visited for (int j = 0; j <= leaves; j++) { if (j % strength_i == 0) visited[j] = true; } } // Iterating over all the leaves // and if the leaf is not visited, increasing // our count by 1 int unvisitedLeavesCount = 0; for (int i = 0; i <= leaves; ++i) { if (!visited[i]) { unvisitedLeavesCount++; } } return unvisitedLeavesCount; } // Drivers code public static void main(String[] args) { int N = 3; int leaves = 6; int[] frogs = {3, 6, 2}; // Function call System.out.println(unvisitedLeaves(N, leaves, frogs)); }} |
Python
def unvisitedLeaves(N, leaves, frogs): # Initializing visited list for leaves, and # marking them as not visited initially visited = [False] * (leaves + 1) # Iterating over all frogs for i in range(N): strength_i = frogs[i] # Going through all the leaves ith frog # will visit and mark the leaves as visited for j in range(leaves + 1): if j % strength_i == 0: visited[j] = True # Iterating over all the leaves # and if the leaf is not visited, increasing # our count by 1 unvisitedLeavesCount = 0 for i in range(leaves + 1): if not visited[i]: unvisitedLeavesCount += 1 return unvisitedLeavesCount# Driver codeif __name__ == "__main__": N = 3 leaves = 6 frogs = [3, 6, 2] # Function call print(unvisitedLeaves(N, leaves, frogs)) |
C#
// C# Implementation:using System;public class GFG{ static int UnvisitedLeaves(int N, int leaves, int[] frogs) { // Initialising visited array for leaves and // marking them as not visited initially bool[] visited = new bool[leaves + 1]; // Iterating over all frogs for (int i = 0; i < N; ++i) { int strength_i = frogs[i]; // Going through all the leaves ith frog // will visit and mark the leaves as visited for (int j = 0; j <= leaves; j++) { if (j % strength_i == 0) visited[j] = true; } } // Iterating over all the leaves // and if the leaf is not visited, increasing // our count by 1 int unvisitedLeavesCount = 0; for (int i = 0; i <= leaves; ++i) { if (!visited[i]) { unvisitedLeavesCount++; } } return unvisitedLeavesCount; } // Drivers code public static void Main(string[] args) { int N = 3; int leaves = 6; int[] frogs = { 3, 6, 2 }; // Function call Console.WriteLine(UnvisitedLeaves(N, leaves, frogs)); }}// This code is contributed by Sakshi |
Javascript
function GFG(N, leaves, frogs) { // Initialising visited array for the leaves and // marking them as not visited initially const visited = new Array(leaves + 1).fill(false); // Iterating over all frogs for (let i = 0; i < N; ++i) { const strength_i = frogs[i]; for (let j = 0; j <= leaves; j++) { if (j % strength_i === 0) visited[j] = true; } } // Iterating over all the leaves // and if the leaf is not visited // increasing our count by 1 let unvisitedLeavesCount = 0; for (let i = 0; i <= leaves; ++i) { if (!visited[i]) { unvisitedLeavesCount++; } } return unvisitedLeavesCount;}// Driver codeconst N = 3;const leaves = 6;const frogs = [3, 6, 2];// Function callconsole.log(GFG(N, leaves, frogs)); |
2
Time Complexity: O(N.leaves)
Auxiliary Space: O(N)
Efficient Approach: To solve the problem using the Sieve Approach:
Since each frog is crossing the pond, there will be leaves that have been visited by another frog already. For those leaves, we do not need to traverse the ponds for such a frog for marking the leaves it visits as true, as they have already been marked true by a frog before it.
Let’s take an example: N = 3 , leaves = 6 , frogs = [ 3, 6, 2 ]
Let’s look for the first frog with strength 3 :
It jumps to 3, then 6, then so on until it reaches the other side of the pond, in this case after 6, in the next jump it reaches the other side.
Now for the next frog with strength 6:
the
In the first jump, it goes to 6 and marks it as visited. Now if the leaves were more, we can observe that since 3 (strength of frog 1) is a factor of 6(strength of frog 2), frog 1 will visit all the leaves that frog 2 will visit. Thus we can skip the iteration for frog 2, and still mark all the leaves that were going to be visited.
Follow the steps to solve the problem:
- Sort Strength in increasing order
- Initialize the visited vector of size leaves+1, and mark them as false
- Initialize the count of unvisited leaves by the total number of leaves
- For each frog, check if the leaf jumped on after the first jump of the frog visited or not. (If in the first jump, it reaches the other end, skip this frog as well, as it will not visit any leaves). If it is visited, skip the iteration for this frog. Else, iterate over all the leaves this frog is going to, mark them as visited, and decrease the number of unvisited leaves by 1.
Below is the implementation for the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;int unvisitedLeaves(int N, int leaves, int frogs[]){ // Initialising visited vector for leaves, // and marking them as not vistied initially vector<bool> visited(leaves + 1, false); // Intialising unvisited leaevs count by total // number of leaves int unvisitedLeavesCount = leaves; // Sorting strength of frogs in increasing order sort(frogs, frogs + N); // Iterating over all frogs for (int i = 0; i < N; ++i) { int strength_i = frogs[i]; // If strength is 1, the frg is going to // visit all leaves so we can return 0, // since no leaves is going to be left unvisited if (strength_i == 1) return 0; // Skipping iteration for this frog as it // will not visit any leaf if (strength_i > leaves) continue; // Skipping iteration as leaves for this // frog are already visited if (visited[strength_i] == true) continue; // If leaves of this frog are not visited // We go through all the leaves ith frog // will visit and mark the leaves as visited for (int j = strength_i; j <= leaves; j += strength_i) { // Decreasing number of leaves not // visited by 1 if the leaf is not visited // in any jump of other frog if (visited[j] == false) unvisitedLeavesCount--; // Marking leaf as visited visited[j] = true; } } return unvisitedLeavesCount;}// Drivers codeint main(){ int N = 3; int leaves = 6; int frogs[N] = { 3, 6, 2 }; // Function call cout << unvisitedLeaves(N, leaves, frogs) << endl; return 0;} |
Java
import java.util.Arrays;public class Main { // Function to calculate the number of unvisited leaves static int unvisitedLeaves(int N, int leaves, int[] frogs) { // Initializing visited array for leaves and marking them as not visited initially boolean[] visited = new boolean[leaves + 1]; // Initializing unvisited leaves count by the total number of leaves int unvisitedLeavesCount = leaves; // Sorting the strength of frogs in increasing order Arrays.sort(frogs); // Iterating over all frogs for (int i = 0; i < N; ++i) { int strength_i = frogs[i]; // If strength is 1, the frog is going to visit all leaves, // so we can return 0 since no leaves will be left unvisited if (strength_i == 1) return 0; // Skipping iteration for this frog as it will not visit any leaf if (strength_i > leaves) continue; // Skipping iteration as leaves for this frog are already visited if (visited[strength_i]) continue; // If leaves of this frog are not visited, // we go through all the leaves ith frog will visit and mark the leaves as visited for (int j = strength_i; j <= leaves; j += strength_i) { // Decreasing the number of leaves not visited by 1 if the leaf is not visited // in any jump of other frogs if (!visited[j]) unvisitedLeavesCount--; // Marking leaf as visited visited[j] = true; } } return unvisitedLeavesCount; } // Driver code public static void main(String[] args) { int N = 3; int leaves = 6; int[] frogs = {3, 6, 2}; // Function call System.out.println(unvisitedLeaves(N, leaves, frogs)); }} |
Python3
# Python code for the above approach:def unvisited_leaves(N, leaves, frogs): # Initializing visited list for leaves, # and marking them as not visited initially visited = [False] * (leaves + 1) # Initializing unvisited leaves count by the total # number of leaves unvisited_leaves_count = leaves # Sorting the strength of frogs in increasing order frogs.sort() # Iterating over all frogs for i in range(N): strength_i = frogs[i] # If strength is 1, the frog is going to # visit all leaves, so we can return 0 if strength_i == 1: return 0 # Skipping iteration for this frog as it # will not visit any leaf if strength_i > leaves: continue # Skipping iteration as leaves for this # frog are already visited if visited[strength_i]: continue # If leaves of this frog are not visited # we go through all the leaves this frog # will visit and mark the leaves as visited for j in range(strength_i, leaves + 1, strength_i): # Decreasing the number of leaves not # visited by 1 if the leaf is not visited # in any jump of other frog if not visited[j]: unvisited_leaves_count -= 1 # Marking the leaf as visited visited[j] = True return unvisited_leaves_count# Driver codeif __name__ == "__main__": N = 3 leaves = 6 frogs = [3, 6, 2] # Function call print(unvisited_leaves(N, leaves, frogs)) |
2
Time Complexity: O(N.log(N) + N*leaves*log(log(leaves))), N.log(N) for sorting strength of frogs. N*(leaves*log(log(leaves))) for iterating over the leaves. So the total time complexity would be a max of N.log(N), N*(leaves*log(log(leaves))).
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
