Amazon SDE-1/2/SDE-Intern OA Questions | Kumar K | December 2025 |Set 215

Question

A large distributed system records n sequential log events, each tagged with a unique timestamp ID from 1 to n.

 

During an audit, engineering teams discovered a subtle issue:

some pairs of logs occur too close together, but not close enough to be flagged by ordinary duplicate detectors.

 

To identify these suspicious pairs, a new rule is introduced:

 

Rule:

A pair of log IDs (i,j), where 1&le;i<j&le;n, is considered suspicious if the ratio of their timestamps satisfies:

1&le;i/j<2

 

This means:

log j is at least as large as log i,

but less than twice its value,

making them &ldquo;near-duplicates&rdquo; in audit terminology.

 

Your task is to determine how many such suspicious log pairs exist

Constraints :

1 &le; n &le; 10^12

 

 

Got this problem on (Citadel)Quant OA.

 

Solved it successfully using the divisor(hyperbola) trick

 

long long solve(long long n){

    long long count=0;

    for(long long i=1; i<=n ; i++){

        long long L= i+1;

        long long R= min(n, 2*i-1);

        

        if(L<=R)

            count+= (R-L+1);

        

    }

    return count;

    

}

 

Is this the expected approach?