Application of Modular Arithmetic

 

Q: If you have x,y,n. and you have to find a number k between 0<=n so that,
k%x=y


Approach1(Bruteforce):
1.Check if n%x==y print n
2.if n%x!=y then loop until n%x==y then print n. 

Code:

1. #include <bits/stdc++.h>
2. using namespace std;
3. int main(){
4.  
5. int t;cin>>t;
6. while(t--)
7. {
8. int x,y,n;cin>>x>>y>>n;
10. if(n%x==y)cout<<n<<endl;
11. else
12. {
13. while(n%x!=y)
14. {
15. n--;
16. }
17. cout<<n<<endl;
18. }
19. }
20. }

Approach2(Greedy):
Time Complexity: O(n)

let assume, k=p'*x+y
now, p'=(k-y)/x ; 0<=k<=n;
so p'=floor((k-y)/x)
ans=k=p'*x+y 

Theory Review: 

Code:

1. #include <bits/stdc++.h>
2. using namespace std;
3. int main(){
4.  
5. int t;cin>>t;
6. while(t--)
7. {
8. int x,y,n;cin>>x>>y>>n;
10. int p=floor(n-y)/x;
11. cout<<p*x+y<<endl;
12. }
13. }

Related Problem: https://codeforces.com/contest/1374/problem/A