Given an integer N, representing the number of stairs, valued from 1 to N, and a starting position S, the task is to count the maximum number of unique stairs that can be reached by moving exactly A or B stairs steps forward or backward from any position, any number of times.
Examples:
Input: N = 10, S = 2, A = 5, B = 7
Output: 4
Explanation:
Starting Position S: Stair 2
From Stair 2, it is possible to reach the stairs 7, i.e. ( S + A ), and 9, i.e. (S + B).
From Stair 9, it is possible to reach stair 4, i.e. ( S – A ).
Therefore, the unique number of stairs that can be reached is 4 {2, 4, 7, 9}.Input: N = 10, S = 2, A = 3, B = 4
Output: 10
Approach: The given problem can be solved using BFS traversal technique. Follow the steps below to solve the problem:
- Initialize a queue and an array vis[] of size (N + 1) and initialize it as false.
- Mark the starting node S as visited i.e., vis[S] as 1. Push S into a queue Q.
- Now iterate until Q is not empty and perform the following steps:
- Pop the front element of the queue and store it in a variable, say currStair.
- Consider all 4 possible types of moves from currStair, i.e. {+A, -A, +B, -B}.
- For every new stair, check whether it is a valid and unvisited stair or not. If found to be true, then push it into Q. Mark the stair as visited. Otherwise, continue.
- Finally, count the number of visited stairs using the array vis[].
- After completing the above steps, print the count of visited stairs as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count the number// of unique stairs visitedvoid countStairs(int n, int x, int a, int b){ // Checks whether the current // stair is visited or not int vis[n + 1] = { 0 }; // Store the possible moves // from the current position int moves[] = { +a, -a, +b, -b }; // Initialize a queue queue<int> q; /// Push the starting position q.push(x); // Mark the starting // position S as visited vis[x] = 1; // Iterate until queue is not empty while (!q.empty()) { // Store the current stair number int currentStair = q.front(); // Pop it from the queue q.pop(); // Check for all possible moves // from the current stair for (int j = 0; j < 4; j++) { // Store the new stair number int newStair = currentStair + moves[j]; // If it is valid and unvisited if (newStair > 0 && newStair <= n && !vis[newStair]) { // Push it into queue q.push(newStair); // Mark the stair as visited vis[newStair] = 1; } } } // Store the result int cnt = 0; // Count the all visited stairs for (int i = 1; i <= n; i++) if (vis[i] == 1) cnt++; // Print the result cout << cnt;}// Driver Codeint main(){ int N = 10, S = 2, A = 5, B = 7; countStairs(N, S, A, B); return 0;} |
Java
// Java program for the above approachimport java.util.LinkedList;import java.util.Queue;class GFG{// Function to count the number// of unique stairs visitedstatic void countStairs(int n, int x, int a, int b){ // Checks whether the current // stair is visited or not int[] vis = new int[n + 1]; // Store the possible moves // from the current position int[] moves = { +a, -a, +b, -b }; // Initialize a queue Queue<Integer> q = new LinkedList<Integer>(); /// Push the starting position q.add(x); // Mark the starting // position S as visited vis[x] = 1; // Iterate until queue is not empty while (!q.isEmpty()) { // Store the current stair number int currentStair = q.peek(); // Pop it from the queue q.remove(); // Check for all possible moves // from the current stair for(int j = 0; j < 4; j++) { // Store the new stair number int newStair = currentStair + moves[j]; // If it is valid and unvisited if (newStair > 0 && newStair <= n && vis[newStair] == 0) { // Push it into queue q.add(newStair); // Mark the stair as visited vis[newStair] = 1; } } } // Store the result int cnt = 0; // Count the all visited stairs for(int i = 1; i <= n; i++) if (vis[i] == 1) cnt++; // Print the result System.out.print(cnt);}// Driver Codepublic static void main(String args[]){ int N = 10, S = 2, A = 5, B = 7; countStairs(N, S, A, B);}}// This code is contributed by abhinavjain194 |
Python3
# Python3 program for the above approachfrom collections import deque# Function to count the number# of unique stairs visiteddef countStairs(n, x, a, b): # Checks whether the current # stair is visited or not vis = [0] * (n + 1) # Store the possible moves # from the current position moves = [+a, -a, +b, -b] # Initialize a queue q = deque() # Push the starting position q.append(x) # Mark the starting # position S as visited vis[x] = 1 # Iterate until queue is not empty while (len(q) > 0): # Store the current stair number currentStair = q.popleft() # Pop it from the queue # q.pop() # Check for all possible moves # from the current stair for j in range(4): # Store the new stair number newStair = currentStair + moves[j] # If it is valid and unvisited if (newStair > 0 and newStair <= n and (not vis[newStair])): # Push it into queue q.append(newStair) # Mark the stair as visited vis[newStair] = 1 # Store the result cnt = 0 # Count the all visited stairs for i in range(1, n + 1): if (vis[i] == 1): cnt += 1 # Print the result print (cnt)# Driver Codeif __name__ == '__main__': N, S, A, B = 10, 2, 5, 7 countStairs(N, S, A, B)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to count the number// of unique stairs visitedstatic void countStairs(int n, int x, int a, int b){ // Checks whether the current // stair is visited or not int []vis = new int[n + 1]; Array.Clear(vis, 0, vis.Length); // Store the possible moves // from the current position int []moves = { +a, -a, +b, -b }; // Initialize a queue Queue<int> q = new Queue<int>(); /// Push the starting position q.Enqueue(x); // Mark the starting // position S as visited vis[x] = 1; // Iterate until queue is not empty while (q.Count > 0) { // Store the current stair number int currentStair = q.Peek(); // Pop it from the queue q.Dequeue(); // Check for all possible moves // from the current stair for(int j = 0; j < 4; j++) { // Store the new stair number int newStair = currentStair + moves[j]; // If it is valid and unvisited if (newStair > 0 && newStair <= n && vis[newStair] == 0) { // Push it into queue q.Enqueue(newStair); // Mark the stair as visited vis[newStair] = 1; } } } // Store the result int cnt = 0; // Count the all visited stairs for(int i = 1; i <= n; i++) if (vis[i] == 1) cnt++; // Print the result Console.WriteLine(cnt);}// Driver Codepublic static void Main(){ int N = 10, S = 2, A = 5, B = 7; countStairs(N, S, A, B);}}// This code is contributed by ipg2016107 |
Javascript
<script>// Javascript program for the above approach// Function to count the number// of unique stairs visitedfunction countStairs(n, x, a, b){ // Checks whether the current // stair is visited or not var vis = Array(n+1).fill(0); // Store the possible moves // from the current position var moves = [ +a, -a, +b, -b ]; // Initialize a queue var q = []; /// Push the starting position q.push(x); // Mark the starting // position S as visited vis[x] = 1; // Iterate until queue is not empty while (q.length!=0) { // Store the current stair number var currentStair = q[0]; // Pop it from the queue q.shift(); // Check for all possible moves // from the current stair for (var j = 0; j < 4; j++) { // Store the new stair number var newStair = currentStair + moves[j]; // If it is valid and unvisited if (newStair > 0 && newStair <= n && !vis[newStair]) { // Push it into queue q.push(newStair); // Mark the stair as visited vis[newStair] = 1; } } } // Store the result var cnt = 0; // Count the all visited stairs for (var i = 1; i <= n; i++) if (vis[i] == 1) cnt++; // Print the result document.write( cnt);}// Driver Codevar N = 10, S = 2, A = 5, B = 7;countStairs(N, S, A, B);</script> |
Output:
4
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
