fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	static int shortestSatisfyingSubarrayFreq(int[] arr, int k){
  11. 		int ans=0;
  12. 		int minLength = Integer.MAX_VALUE;
  13. 		for(int start=0; start<arr.length; start++){
  14.  
  15. 			int sum=0;
  16. 			for(int end=start; end<arr.length; end++){
  17. 				sum +=arr[end];
  18. 				if(sum==k){
  19. 					if((end-start+1)==minLength){
  20. 						ans++;
  21. 					} else if ((end-start+1)<minLength) {
  22. 						minLength = (end-start+1);
  23. 						ans = 1;
  24. 					}
  25. 				}
  26. 			}
  27. 		}
  28. 		return minLength==Integer.MAX_VALUE ? 0 : ans;
  29. 	}
  30.  
  31. 	static int longestSatisfyingSubarrayFreq(int[] arr, int k){
  32. 		int ans=0;
  33. 		int maxLength = Integer.MIN_VALUE;
  34. 		for(int start=0; start<arr.length; start++){
  35.  
  36. 			int sum=0;
  37. 			for(int end=start; end<arr.length; end++){
  38. 				sum +=arr[end];
  39. 				if(sum==k){
  40. 					if((end-start+1)==maxLength){
  41. 						ans++;
  42. 					} else if ((end-start+1)>maxLength) {
  43. 						maxLength = (end-start+1);
  44. 						ans = 1;
  45. 					}
  46. 				}
  47. 			}
  48. 		}
  49. 		return maxLength==Integer.MIN_VALUE ? 0 : ans;
  50. 	}
  51. 	public static void main (String[] args) throws java.lang.Exception
  52. 	{
  53. 		// Find count of shortest/largest subarrays with sum k in given array
  54.  
  55. 		Scanner sc = new Scanner(System.in);
  56. 		int arrLength = sc.nextInt();
  57. 		int[] arr = new int[arrLength];
  58. 		for(int i=0; i<arrLength; i++){
  59. 			arr[i] = sc.nextInt();
  60. 		}
  61. 		int k = sc.nextInt();
  62.  
  63. 		/*	use example
  64. 	        10
  65. 	        0 5 -5 3 2 1 0 6 -1 5
  66.         	5
  67.         	// freq of shortest length subarray having sum = k is :2
  68. 		*/
  69.  
  70. 		System.out.println("freq of shortest length subarray having sum = k is :"+ 
  71. 		shortestSatisfyingSubarrayFreq(arr, k));
  72. 		System.out.println("freq of longest length subarray having sum = k is :"+ 
  73. 		longestSatisfyingSubarrayFreq(arr, k));
  74. 	}
  75. }
Success #stdin #stdout 0.13s 56912KB
comments (?)
stdin
copy 
10
0 5 -5 3 2 1 0 6 -1 5
5
stdout
copy 
freq of shortest length subarray having sum = k is :2
freq of longest length subarray having sum = k is :1
https://ideone.com/OvRSky
language:
Java (HotSpot 12)
created:
3 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!