Somebody help me on CSUM problem JAVA?

I tried many times and the solution is working in my IDE but it doesn’t work in codechef.

This is the first solution :

https://www.codechef.com/viewsolution/24861984

The above solution was partially correct and i was getting TLE on subtasks. So i tried following
solution :

https://www.codechef.com/viewsolution/24868574

This solution is giving me NZEC.

This is frustrating, i am trying this question from 3 days now still with no success. I am discouraged to continue further on platform.

Any help or suggestions will be appreciated, i am aim to have good command over DS & Algos. This question was the starting point for me. :frowning_face:

https://www.codechef.com/viewsolution/24861984 : TLE (Better solution required, O(nlg n))
https://www.codechef.com/viewsolution/24868574 : It’s not an NZEC, it’s a compilation error (Check the spelling of “import” in the very first line)

1 Like

I tried to solve it but I’m getting some error as well. I’m unable to identify it
My solution: https://www.codechef.com/viewsolution/28377056

Don’t be discouraged my friend, starts are always frustating. I went through your code, but logic seems very confusing, that’s why it must be failing on strong test cases.
In these scenarios you need to find out which test cases ur solution will fail.

since range of n is till 10^4 , we need to solve this in O( n log n )

first step u did correct by sorting the array.
second step is where optimization is need in searching. and most optimized search algorithm is ?

Binary Search

so iterate through sorted array

for element a , check if a - k exists in array using binary search of log( n )

so for n elements, it will take n * log n time in total

1 Like

Thanks mate, as suggest by you i have sorted the array and then used binary search. Test cases are now passed.

Thanks for motivation.

public static void main (String[]args) throws java.lang.Exception
  {
    // your code goes here
    Scanner in = new Scanner (System.in);
    int t = in.nextInt ();
    for (int i = 0; i < t; i++)
      {
        int n=in.nextInt();
        int k=in.nextInt();
        int[] a=new int[n];
        for (int j=0;j<n;j++) 
        {
            a[j]=in.nextInt();
        }
        Arrays.sort(a);
        int r=-1;
        for (int j=0;j<n;j++)
        {
            if (a[j]>=k) r=j-1;
        }
        if (r==-1) r=n-1;
        int req=k-a[r];
        Boolean con=false;
        int j=0;
        while (!con && a[r]>=k/2)
        {
          if (a[j]==req) 
          {
              con=true;
          }
          else if (j<r-1)
          {
              j++;
              continue;
          }
          else if (r>1)
          {
              j=0;
              r--;
              req=k-a[r];
              continue;
          }
            break;
            
        }
        
        if (con) System.out.println("Yes");
        else System.out.println("No");
      }
  }

This is how I did it in Java. My logic is that I find the largest number smaller than k. Then that number subtracted from k will be the other number that I require, if that number exists in the array, then my condition is satisfied and if not then I check for the number smaller than the one I used before

Don’t forget to sort the Array