Solution 4 for Scaler Topics Fortnightly Contest

This article is part of the Scaler Topics Fortnightly Contest - 3.

Build an AI-First Career, Master the Complete Skillset

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

Go to Program

NSDC Certified

AI Forward Deployed Engineer Program

Full-stack engineering, production AI and client-facing consulting

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

Solution Approach

Pre-requisite: Binary Lifting and Prime Factorization using Sieve of Eratosthenes.
The idea is to find the next catcher for every robot and then travel on the path that it makes.
For the first part, i.e. finding the next catcher, we can first prime factorize each array element using Sieve. This takes O(NloglogN) time for precomputation and O(logN) time for each prime factorization. Normal prime factorization will take O(sqrt(N)) time for each prime factorization.
After finding the prime factors, we can simply traverse all the prime factors for each element and check if any index ahead of the current index has that prime factor. Our next catcher would be the minimum index ahead of the current index, which has any common factor.
Once we have stored the next catcher for every index, we can travel on the path made by them.
For each query, we can travel on the path made by the series of next catchers, but it will take O(N) time for each query in the worst case.
So, we can use the technique of Binary Lifting to travel on these parts in O(log N) time complexity.