fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class Codechef
  6. {
  7.     private static int [] f;
  8. 	public static void main (String[] args) throws java.lang.Exception
  9. 	{
  10. 		// your code goes here
  11. 		// arr = [1,1,1,1,1]
  12. 		// ---> f[] = [0,5,9];
  13. 		Scanner sc=new Scanner(System.in);
  14. 		int t=sc.nextInt();
  15. 		int j=1;
  16. 		while(t-->0){
  17. 		    int n=sc.nextInt();
  18. 		    int k=sc.nextInt();
  19. 		    int [] arr=new int[n];
  20. 		    for(int i=0;i<n;i++){
  21. 		        arr[i]=sc.nextInt();
  22. 		    }
  23. 		    int sum=solve(arr,k);
  24. 		    System.out.println("Case #"+j+" : "+sum);
  25. 		    j++;
  26. 		}
  27. 		sc.close();
  28. 	}
  29.  
  30. 	public static int solve(int []nums,int k){
  31. 	    int n=nums.length;
  32. 	    int maxSum=0;
  33. 	    for(int num : nums){
  34. 	        maxSum+=num;
  35. 	    }
  36. 	    f=new int[maxSum];
  37. 	    f[0]=0;
  38. 	    for(int i=1;i<f.length;i++){
  39. 	        f[i]=contiguousSubarray(nums,i)+f[i-1];
  40. 	        if(f[i]>k){
  41. 	            return i;
  42. 	        }else if(f[i]==k){
  43. 	            return i;
  44. 	        }
  45. 	    }
  46. 	    return -1;
  47.  
  48. 	}
  49.  
  50. 	public static int contiguousSubarray(int[] nums,int target) {
  51.         Map<Integer, Integer> map = new HashMap<>();
  52.         int sum = 0;
  53.         int count = 0;
  54.         map.put(0, 1);
  55.  
  56.         for (int num : nums) {
  57.             sum += num;
  58.             int find=sum-target;
  59.             if (map.containsKey(find)) {
  60.                 count += map.get(find);
  61.             }
  62.  
  63.             map.put(sum, map.getOrDefault(sum, 0) + 1);
  64.         }
  65.  
  66.         return count;
  67.     }
  68. }
  69.  
Success #stdin #stdout 0.24s 58832KB
comments (?)
stdin
copy 
6
5 6
1 1 1 1 1
5 3
1 2 3 4 5
4 5
2 2 2 2
1 1
10
3 6
1 2 3
4 1
1 3 6 10
stdout
copy 
Case #1 : 2
Case #2 : 3
Case #3 : 4
Case #4 : -1
Case #5 : -1
Case #6 : 1
https://ideone.com/QeoUAc
language:
Java (HotSpot 12)
created:
17 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!