Please check anyone why this code is not working
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void solve(){
int n; cin>>n;
vector<int> arr(n);
vector<int> con(101, 0);
int ans = 0;
int pairs = 0;
for(int i = 0; i<n; i++){
cin>>arr[i];
con[arr[i]]++;
}
if(n == 1)
cout<<3<<endl;
else if(n == 2)
cout<<2<<endl;
else if(n>2){
for(int i = 0; i<101; i++){
if(con[i]%2){
con[i]+=1;
ans++;
}
if(con[i] != 0)
pairs++;
}
if(pairs == 1)
cout<<ans<<endl;
else if(pairs%2 == 0 && pairs>1)
cout<<ans<<endl;
else
cout<<ans+2<<endl;
}
}
int main(){
int t; cin>>t;
while(t--){
solve();
}
return 0;
}
thanks bhai:heartpulse:
i forgot about this case
Hey @saiyan_god 
,
your code is half correct but while(sticks>0) part has logic error also you don’t need to do this much till part where you counted extra for every odd count of number then just think that every even pair will contribute towards two side of rectangle so all you need after calculating extra is just check (size of array + extra ) is divisible by 4 or not this sum will always be even because for every number that counted odd has now a new number with which it became even so whole (size of array + extra) is even now.
We just need to check if((size of array + extra)%4==0 ) if not and we know this will be even that means remainder has 2 so we add 2 and we got our answer.
Here is my code.
#include <iostream>
#include<bits/stdc++.h>
#include<deque>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<stdio.h>
#include<bitset>
#include<string>
#include<vector>
#include<unordered_map>
#include<queue>
#include<set>
#include<fstream>
#include<map>
#define int long long int
#define ld long double
#define pi 3.1415926535897932384626433832795028841971
#define MOD 1000000007
#define MOD1 998244353
#define print(vec) for (int i = 0; i < vec.size(); i++) cout << vec[i] << " "; cout << "\n";
using namespace std;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int inf = 1e18;
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
#ifdef __SIZEOF_INT128__
ostream& operator << (ostream &os, __int128 const& value) {
static char buffer[64];
int index = 0;
__uint128_t T = (value < 0) ? (-(value + 1)) + __uint128_t(1) : value;
if (value < 0)
os << '-';
else if (T == 0)
return os << '0';
for (; T > 0; ++index) {
buffer[index] = static_cast<char>('0' + (T % 10));
T /= 10;
}
while (index > 0)
os << buffer[--index];
return os;
}
istream& operator >> (istream& is, __int128& T) {
static char buffer[64];
is >> buffer;
size_t len = strlen(buffer), index = 0;
T = 0; int mul = 1;
if (buffer[index] == '-')
++index, mul *= -1;
for (; index < len; ++index)
T = T * 10 + static_cast<int>(buffer[index] - '0');
T *= mul;
return is;
}
#endif
int add(long long a, long long b) {return ((a % MOD) + (b % MOD)) % MOD;}
int subtract(long long a, long long b) {return ((a % MOD) - (b % MOD)) % MOD;}
int mult(long long a, long long b) {return ((a % MOD) * (b % MOD)) % MOD;}
int add1(long long a, long long b) {return ((a % MOD1) + (b % MOD1)) % MOD1;}
int subtract1(long long a, long long b) {return ((a % MOD1) - (b % MOD1)) % MOD1;}
int mult1(long long a, long long b) {return ((a % MOD1) * (b % MOD1)) % MOD1;}
int expo(int a, int b, int mod) {
int res = 1;
while (b > 0)
{ if (b & 1)
res = (res * a) % mod;
a = (a * a) % mod;
b = b >> 1;
} return res;
}
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
int mminvprime(int a, int b) {
return expo(a, b, b + 2);
}
int32_t main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
map<int, int> m;
for (int i = 0; i < n; ++i)
{
int x;
cin >> x;
m[x]++;
}
int count = 0;
for (auto x : m)
{
if (x.second % 2)
{
count++;
}
}
int sum = n + count;
if (sum % 4 != 0) sum += sum % 4;
//since we need count of new elements added we subtracted total - original elements
cout << sum - n << "\n";
}
return 0;
}
1 Like