Leetcode75/ValidPair.cpp at main · IshikaOG/Leetcode75 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ff                 first
#define ss                 second
#define endl               "\n"
#define ll                 long long
#define ld                 long double
#define loop(a, b, c)      for(ll (a) = (b); (a)<=(c); (a)++)
#define looprev(a, b, c)   for(ll (a) = (b); (a)>=(c); (a)--)
#define pb                 push_back
#define mp                 make_pair
#define pii                pair<ll, ll>
#define vi                 vector<ll>
#define mii                map<ll, ll>
#define ump                unordered_map<ll, ll>
#define pqb                priority_queue<ll>
#define pqs                priority_queue<int, vi, greater<ll> >
#define setbits(x)         __builtin_popcountll(x)
#define zrobits(x)         __builtin_ctzll(x)
#define mod                1000000007
#define inf                1e18
#define ps(x, y)           fixed<<setprecision(y)<<x
#define mk(arr,n,type)     type *arr = new type[n];
#define w(t)               int x; cin>>x; while(x--)
// mt19937                    rng(chrono::steady_clock::now,time_since_epoch(),count());
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> pbds;


void file_i_o(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	/* #ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif */
}


/*
bool isValidPair(vector<int> &arr, int n, int k, int m) {
    // Write your code here.

    if(n%2 == 1) return false;

	for(int i = 0; i < n; i++) {

		if(arr[i] == -1) continue;

		for(int j = i+1; j < n; j++) {

			if(arr[j] == -1) continue;

			if((arr[i] + arr[j]) % k == m) {
				arr[i] = -1;
				arr[j] = -1;
				break;
			}
		}
	}

	for(int i = 0; i < n; i++) {
		if(arr[i] != -1) return false;
	}

	return true;
}*/


bool isValidPair(vector<int> &arr, int n, int k, int m) {

	unordered_map<int, int> freq;

	if(n%2 == 1) return false;


	for(int i = 0; i < n; i++) {
		freq[arr[i]%k]++;
	}

	for(auto it = freq.begin(); it != freq.end(); it++) {
		int A = it->first;

		int x = (m - A+k)%k;

		if(freq[x] != freq[A]) return false;
	}

	return true;

}


int main(int argc, char const *argv[]) {

	file_i_o();

	clock_t start, end;
    start = clock();

	w(t){

	/*  Write Code Here  */

		int n;
		cin >> n;

		vector<int> arr(n);

		for(int i = 0; i < n; i++) {
			cin >> arr[i];
		}

		int k, m;
		cin >> k >> m;

		if(isValidPair(arr, n, k, m)){
			cout << 'true' << endl;
		}
		else {
			cout << 'false' << endl;
		}


	}

	end = clock();

	double time_taken=double(end-start)/double(CLOCKS_PER_SEC);
    cerr<<"\nTime : "<<fixed<<time_taken<<setprecision(5)<<" s \n";
    cerr<<"\n"<< "Coded By : S!r Black-D3vil" <<"\n";

	return 0;
}