Recently I gave Amazon coding test, in which i got the following question —<br/> ↵
↵
Given n, find all numbers from 1 to n, which are coprime with n.↵
ex.<br/>↵
ex.<br/>↵
Input: n = 5 <br/>↵
Output: 4 <br/>↵
Explanation — The numbers coprime with n = 5 are (1,5), (2,5), (3,5), (4,5)↵
↵
Input: n = 10↵
Output: 4 <br/>↵
Output: 4 <br/>↵
Explanation — (1,10), (3,10), (7,10), (9,10)↵
↵
Constraints 1 <= n <= 10^9.↵
↵
I wrote a brute force solution, where i took each numebr from 1 to n and tried to find its gcd with n. Which apparently gave a TLE on most of the test cases.↵
↵
Can anyone kindly guide me how to solve this problem ?↵
↵
Given n, find all numbers from 1 to n, which are coprime with n.
ex.
ex.<br/>↵
Input: n = 5 <br/>↵
Output: 4 <br/>↵
Explanation — The numbers coprime with n = 5 are (1,5), (2,5), (3,5), (4,5)↵
↵
Input: n = 10
Output: 4
Output: 4 <br/>↵
Explanation — (1,10), (3,10), (7,10), (9,10)↵
↵
Constraints 1 <= n <= 10^9.↵
↵
I wrote a brute force solution, where i took each numebr from 1 to n and tried to find its gcd with n. Which apparently gave a TLE on most of the test cases.↵
↵
Can anyone kindly guide me how to solve this problem ?↵
