@akhii1998 The reason you got WA is because you are storing the product of a[i] & a[j] in the integer variable whereas integer limit is 2 * 10^9 and product can go about 10^18. However, that is not you should be worried about. Since you are beginner I think you are not yet aware of the term Time Complexity .( check this links or search on web to know about Time Complexity: https://www.quora.com/What-are-some-easy-ways-to-understand-and-calculate-the-time-complexity-of-algorithms https://www.quora.com/I-am-getting-âTime-Limit-Exceededâ-response-for-several-problems-on-Codechef-How-should-I-optimize-my-code/answer/Vaibhav-Tulsyan ) You are running two loops to choose a[i] and a[j] and size of the array can be upto 10^5 . Then 2 select every 2 combination you are using 10^5 Choose 2 iteration which is in the order of 10^10. And again you are linear searching , suppose the product is not present in array, then you have to again traverse 10^5 elements. So your complexity can go up-to 10^15 iterations which can take years to execute because normally PC executes 10^8 to 10^9 iterations per second of C/C++ code.
Hence, to reduce the time complexity you need to think about other logic, better logic than needs few number of iterations. So try your best to come up with better approach by making some observations(Use pen and notebook :P). And, if stuck can have a look at working solution here : https://www.codechef.com/viewsolution/ .
Cheers , happy coding and learning .
anbody can help me why my code is wrong?
#include<stdio.h>
int main()
{
int a,b,c,d,k,h=0,y,i=1,j[100000];
scanf("%d\n",&a);
start:scanf("%d\n",&b);
d=b-1;
y=b;
while(b!=0)
{
scanf("%d",&c);
j[i]=c;
i++;
b--;
}
for(i=1;d>=1;d--,i++)
{
k=j[i];
k=k*j[i+1];
}
for(i=1;i<=y;i++)
{
if(k==j[i])
{
h++;
}
}
if(h!=0)
{
printf("yes\n");
a--;
}
else if(h>0)
{
printf("no\n");
a--;
}
if(a!=0)
{
goto start;
}
return 0;
}
I have a problem with this task !
I have another solution more complicated
i have tested for several examples and it works , but every time i submitt , it gives âwrong answerâ , i donât know why ?!!
package beginner;
import java.io.;
import java.util.;
import java.lang.*;
public class BeautifulArraysICPC16B {
// static int max ;
// static int min;
// static int occMax ;
// static int occMin ;
static class InputReader {
public BufferedReader buff;
public StringTokenizer token;
public InputReader(InputStream stream) {
buff = new BufferedReader(new InputStreamReader(stream), 32768);
token = null;
}
public String next() {
while (token == null || !token.hasMoreTokens()) {
try {
token = new StringTokenizer(buff.readLine());
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
return token.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
public static int max(int[] tab){
int max = tab[0];
for(int i=0 ; i< tab.length ;i++){
if(tab[i] > max) {max = tab[i] ;}
}
return max;
}
public static int min(int[] tab){
int min = tab[0];
for(int i=0 ; i< tab.length ;i++){
if(tab[i] < min) {min = tab[i] ;}
}
return min;
}
public static int firstocc(int[] tab , int a){
int j = -1 ;
do{
j++;
}while(tab[j]!=a && j <tab.length);
if(j< tab.length) return j ;
else return -1;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
int T = in.nextInt();
for (int i = 0 ; i < T ; i++){
int n = in.nextInt();
int[] tab = new int[n];
for(int j=0 ; j< tab.length ; j++){
tab[j] = in.nextInt();
}
int max = max(tab);
int min = min(tab);
int occMax = firstocc(tab, max);
int occMin = firstocc(tab, min);
boolean t = true ;
// if(n==1) {
// out.println(ânoâ);
// }else
if(max>1){
int l = 0 ;
while(l < tab.length && t){
if(l!=occMax){t=(tab[l]==1 || tab[l]==0);}
if(!t){out.println("no");break;}
l++;
}
if (l==tab.length) out.println("yes");
}else if(min<-1){
int l = 0 ;
while(l < tab.length && t){
if(l!=occMin){t=(tab[l]==1 || tab[l]==0);}
if(!t){out.println("no");break;}
l++;
}
if (l==tab.length) out.println("yes");
}else if(min==-1 && max==-1){
out.println("no");
}else{
out.println("yes");
}
}
out.close();
}
}
well i have a doubt in this problem,shouldnât the array for example {1,-1,2} be not beautiful as -1*2 = -2 as there is no such element therefore {1,-1,2} should not be beautiful but in few of the successful submissions this array comes out to be a beautiful array and i submitted both mine(which shows the above example to be not beautiful) and the other codechef seemed to accept the other one.I think there is a problem in the solution from there end MAYBE.So pls somebody help and pls tell where i am going wrong?
#include
using namespace std;
int main() {
int k;
cin>>k;
for(int j=1;j<=k;j++)
{
int n;
cin>>n;
int a[n],sum=1,i,count=0;
for(i=0;i<n;i++)
{
cin>>a[i];
}
for(i=0;i<n;i++)
{
sum*=a[i];
}
for(i=0;i<n;i++){
if(sum==a[i])
{
count++;
}
}
if(count>=1)
{
cout<<"yes"<<endl;
}
else
{
cout<<"no";
}
}
return 0;
}
plsâŚAnyone look at this codeâŚpls tell me what is wrong with this⌠I an getting the correct answer in all other compilers.But code chef states it as wrong answer⌠PLS HELP ANYONEâŚPLSâŚPLSâŚPLSâŚ
import java.util.;
import java.lang.;
import java.io.*;
class BeautifulArray {
public static void main(String args[])throws java.lang.Exception{
Scanner in=new Scanner(System.in);
int testc=in.nextInt();
for(int c=0;c<testc;c++){
int n=in.nextInt();
int i,j,temp=0,k,flag=0,fflag=0;
int a[]=new int[n];
for(i=0;i<n;i++){
a[i]=in.nextInt();
}
for(i=0; i < n; i++){
for(j=1; j < (n-i); j++){
if(a[j-1] > a[j]){
temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
}
}
}
fflag=0;
for(i=1;i<n;i++){
flag=0;
for(j=0;j<=i;j++){
if(a[j]!=0){
if(a[i]%a[j]==0){
for(k=j+1;k<=i;k++){
if(a[i]/a[j]==a[k]){
flag=1;
break;
}
}
if(flag==1)
break;
}
}
}
if(flag==0){
fflag=1;
break;
}
}
if(fflag==1)
System.out.println(ânoâ);
else
System.out.println(âyesâ);
}
}
}
What is wrong in my code?
For n=1, array is beautiful. AFter accounting for this, you will get TLE. Make some observations on when an array can be beautiful. Take an array of-
only 0,
0 and 1
0,1 and >=2 elements with abs(arr[i])>1
These 3 will give you a direction to think.
1 Like