Find the unvisited positions in Array traversal
Given an array A[] of N positive integers where A[i] represent the units each i can traverse in one step. You can start from position 0 and need to reach destination d. The goal is to find the number of positions that are not visited when all of them have reached position d.
Examples:
Input: N = 3, d = 4, A[] = {3, 2, 4}
Output: 1
Explanation: Position 1 will not be visited.Input: N = 3, d = 6, A[] = {1, 3, 5}
Output: 0
Explanation: All positions will be visited.
Approach: To solve the problem follow the below idea:
The intuition is to create a visited array which keeps track of the visited positions and return the number of positions that remains unvisited in the end.
Below are the steps for the above approach:
- Create a visited array of length equal to the number of d +1 and initialize all the elements = 0.
- Start traversing the A[] array.
- Now run a “for” loop for each i and mark the positions that are traversed.
- Make the “positionstatus” == 1 for every visited position and make sure to not visit the already visited position.
- Now traverse the “positionstatus” array and count the number of indexes with value == 0, they are unvisited positions.
- Return the count of unvisited positions.
Below is the code for the above approach:
C++
#include <bits/stdc++.h> using namespace std; int unvisitedpositions( int N, int d, int A[]) { // Create an array to track the // status of each positions int positionStatus[d + 1] = {0}; // Check for each position i if // it is in range and not // visited yet for ( int i = 0; i < N; i++) { if (A[i] <= d && positionStatus[A[i]] == 0) { // Mark all positions that // the i can reach /// as visited for ( int j = A[i]; j <= d; j += A[i]) { positionStatus[j] = 1; } } } // Count the number of // unvisited positions int positionCount = d; for ( int i : positionStatus) { if (i == 1) { positionCount--; } } // Return the count of // unvisited positions return positionCount; } // Drivers code int main() { int N = 3; int d = 4; int A[] = { 3, 2, 4 }; // Function Call int unvisited = unvisitedpositions(N, d, A); cout << unvisited; return 0; } |
Java
// Java code for the above approach: import java.util.*; class GFG { public static int unvisitedpositions( int N, int d, int A[]) { // Create an array to track the // status of each positions int positionStatus[] = new int [d + 1 ]; // Check for each position i if // it is in range and not // visited yet for ( int i = 0 ; i < N; i++) { if (A[i] <= d && positionStatus[A[i]] == 0 ) { // Mark all positions that // the i can reach /// as visited for ( int j = A[i]; j <= d; j += A[i]) { positionStatus[j] = 1 ; } } } // Count the number of // unvisited positions int positionCount = d; for ( int i : positionStatus) { if (i == 1 ) { positionCount--; } } // Return the count of // unvisited positions return positionCount; } // Drivers code public static void main(String[] args) { int N = 3 ; int d = 4 ; int [] A = { 3 , 2 , 4 }; // Function Call int unvisited = unvisitedpositions(N, d, A); System.out.println(unvisited); } } |
Python3
def unvisited_positions(N, d, A): # Create an array to track the # status of each positions position_status = [ 0 ] * (d + 1 ) # Check for each position i if # it is in range and not # visited yet for i in range (N): if A[i] < = d and position_status[A[i]] = = 0 : # Mark all positions that # the i can reach # as visited for j in range (A[i], d + 1 , A[i]): position_status[j] = 1 # Count the number of # unvisited positions position_count = d for i in position_status: if i = = 1 : position_count - = 1 # Return the count of # unvisited positions return position_count # Driver code N = 3 d = 4 A = [ 3 , 2 , 4 ] # Function Call unvisited = unvisited_positions(N, d, A) print (unvisited) |
C#
using System; class MainClass { static int unvisitedpositions( int N, int d, int [] A) { // Create an array to track the // status of each position int [] positionStatus = new int [d + 1]; // Check for each position i if // it is in range and not // visited yet for ( int i = 0; i < N; i++) { if (A[i] <= d && positionStatus[A[i]] == 0) { // Mark all positions that // the i can reach // as visited for ( int j = A[i]; j <= d; j += A[i]) { positionStatus[j] = 1; } } } // Count the number of // unvisited positions int positionCount = d; foreach ( int i in positionStatus) { if (i == 1) { positionCount--; } } // Return the count of // unvisited positions return positionCount; } // Drivers code static void Main() { int N = 3; int d = 4; int [] A = { 3, 2, 4 }; // Function Call int unvisited = unvisitedpositions(N, d, A); Console.WriteLine(unvisited); } } |
Javascript
function unvisitedpositions(N, d, A) { // Create an array to track the // status of each position let positionStatus = new Array(d + 1).fill(0); // Check for each position i if // it is in range and not // visited yet for (let i = 0; i < N; i++) { if (A[i] <= d && positionStatus[A[i]] === 0) { // Mark all positions that // i can reach // as visited for (let j = A[i]; j <= d; j += A[i]) { positionStatus[j] = 1; } } } // Count the number of // unvisited positions let positionCount = d; for (let i of positionStatus) { if (i === 1) { positionCount--; } } // Return the count of // unvisited positions return positionCount; } // Driver code const N = 3; const d = 4; const A = [3, 2, 4]; // Function call const unvisited = unvisitedpositions(N, d, A); console.log(unvisited); |
1
Time Complexity: O(N*logN)
Auxiliary Space: O(positions)