CITADEL OA Internship 2025
- Result
- Ongoing
- Posted
- 22 Aug 2025
Summary
I participated in the Citadel Online Assessment for a 2025 Internship and encountered a challenging algorithmic problem focused on modular arithmetic and combinations.
How it went
During my online assessment for the Citadel 2025 Internship, I was presented with a complex algorithmic problem. The task involved calculating the total sum of C(i,j) = i mod j + j mod i for all 1<=i<=n and 1<=j<=n, with the final sum needing to be returned modulo (10^9 + 7). Although the exact constraints were not provided, it was explicitly stated that an O(n^2) solution would not be efficient enough, indicating a need for a more optimized approach.
Questions asked (1)
- 01
Sum of (i mod j + j mod i) Modulo M
Data Structures & Algorithms · Hard
Given an integer
n, calculate the total sum of all combinationsC(i,j), where(1<=i<=n && 1<=j<=n)and whereC(i,j) = i mod j + j mod i. Since the result can be very large, return the final sum modulo(10^9 + 7).
Function signature:int solve(int n)
Example:
int n = 3
C(3,3) = 3 mod 3 + 3 mod 3 = 0 + 0 = 0
C(3,2) = 3 mod 2 + 2 mod 3 = 1 + 1 = 2
C(3,1) = 3 mod 1 + 1 mod 3 = 2 + 2 = 4
C(2,3) = 2 mod 3 + 3 mod 2 = 1 + 1 = 2
C(2,2) = 2 mod 2 + 2 mod 2 = 0
C(2,1) = 2 mod 1 + 1 mod 2 = 1 + 1 = 2
C(1,3) = 1 mod 3 + 3 mod 1 = 4
C(1,2) = 1 mod 2 + 2 mod 1 = 2
C(1,1) = 1 mod 1 + 1 mod 1 = 0
TotalSum = 0+2+4+2+0+2+4+2+0 = 16
It was noted that an O(n^2) solution would not pass.