Nearest similar number Complete Solution

This article is part of the Scaler Topics Fortnightly Contest - 18

Transform Your Career

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

Solution Approach

• Since we can generate all the prime factors of A, we can check by replacing each prime factor 'P' in its prime factorisation, by a prime number just smaller than P, p1 and a prime numberjust greater than P, p2. Out of them, the number which gives the smallest absolute difference,will be our answer.
• So if abs(A1-A) < abs(A2-A) => return A1 if abs(A1-A) > abs(A2-A) => return A2 if abs(A1-A) = abs(A2-A) => return A2
• There will be some precomputation needed to generate all the prime numbers upto A, which can be done using seive.

Time Complexity: O(N*log(N)) Space Complexity: O(N).

C++ Implementation

Java Implementation

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Python Implementation