I was also stuck on 1st test case . By using your given test case ,i got right answer . Thanks for your help.
Thanks for this corner case my code is failing.
Cāmon! How can you do 8? The max no. of operations you can do is n-1
Solution I solved it without using prefix sumsā¦ Basic idea is iterate through factors of sum in increasing orderā¦ Answer is the least factor which we can make array equal toā¦ Remember thereās a special case if sum is zero
Thanks a lot for pointing out the fault
One thing which I have changed in my solution to make it little bit optimized is to iterate over y not x as x.y=S so y is also a factor and but y has one other bound which is it must be <=n as it is the size of final array which must be <= size of initial array(n).
In my Solution, First I have find out all the factors which are <=n of S then in other for loop for all those number I have checked whether they are valid or not in O(N).
Here is the link for my solution:
https://www.codechef.com/viewsolution/57952211
i am also getting WA on only test case 1.
i tried 45 time but still get WA on test case first .
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef pair<double, double> pd;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pi> vpi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pll> vpll;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<pd> vpd;
typedef vector<string> vs;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORb(i, a, b) for (int i = (a); i >= (b); i--)
#define trav(x, a) for (auto &x : a)
#define travc(x, a) for (auto const &x : a)
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
const int int_max = numeric_limits<int>::max();
const int int_min = numeric_limits<int>::min();
const ll ll_max = numeric_limits<ll>::max();
const ll ll_min = numeric_limits<ll>::min();
const int MOD = 1000000007;
const double PIE = 3.14;
const char nl = '\n';
void setIO(string name = "")
{
ios_base::sync_with_stdio(false);
cin.tie(0);
if (name.size())
{
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
}
void factors(int sum, vi &fac)
{
for (int i = 1; i * i <= abs(sum); i++)
{
if (abs(sum) % i == 0)
{
fac.push_back((sum < 0 ? -i : i));
if (i * i != abs(sum))
fac.push_back(sum / i);
}
}
}
int main()
{
setIO();
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vi v(n + 1);
v[0] = 0;
FOR(i, 1, n + 1)
{
cin >> v[i];
v[i] += v[i - 1];
}
vi fac;
factors(v[n], fac);
if (v[n] == 0)
fac.push_back(0);
int ans = 0;
FOR(i, 0, sz(fac))
{
int lastInd = 0, tempAns = 0;
FOR(j, 1, n + 1)
{
if (fac[i] != 0 && tempAns == abs(v[n] / fac[i]))
break;
if (v[j] - v[lastInd] == fac[i])
{
tempAns++;
lastInd = j;
}
}
ans = max(ans, max(1, tempAns));
}
cout << n - ans << nl;
}
return 0;
}
/***Author: Vishwajeet Prasad***/
Can someone point out, whatās wrong in my code? Itās failing on the testcases 1 and 10.
I am also unable to find any error in my code, giving WA on 1st test case onlyā¦
https://www.codechef.com/viewsolution/57954193
Is there is some issue in first test case as my code works for each and every test case accept first one.
code attached below
solution
for those codes which are failing at testcase 1 only
try these testcases
1 1 1 -1 ans: 2
1 1 1 1 -2 ans: 3
1 1 1 1 1 -3 ans: 4
working fine all the these test cases
import java.io.*;
import java.util.*;
class REMADJ{
public static void main(String args[]) throws IOException,NumberFormatException{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(reader.readLine().replaceAll(" ",""));
while(t>0)
{
int n = Integer.parseInt(reader.readLine().replaceAll(" ",""));
int num=0;
int isEqual=1;
int prev=Integer.parseInt(reader.readLine().replaceAll(" ",""));
int sum=prev;
int max=prev;
for(int i=0; i<n-1; i++){
int input= Integer.parseInt(reader.readLine().replaceAll(" ",""));
//
sum = sum + input;
if(input>max)
max=input;
if(input!=prev)
isEqual=0;
prev=input;
}
if(n==2)
{
System.out.println("1");
return;
}
sum = sum - max;
if(isEqual==1){
// means all elements are equal;
System.out.println(0);
}
else{
System.out.println(sum/max);
}
t--;
}
}
}
https://www.codechef.com/viewsolution/57843892
Can someone tell me why am I getting run time for this solution
@vishwajeet7381
your code gives ans 5 on this testcase but i coudnāt find any way to do it in 5 steps
1
7
1 1 2 3 5 7 -1
sir can you explain why my code is giving SIGSEGV for only one test case but running completely normal on my machine with g++ 9.4.0
this is my solution
https://www.codechef.com/viewsolution/57940893
thanks now i got my mistake