fork download
  1. import java.util.*;
  2. import java.io.*;
  3. public class Main
  4. {
  5. public static int firstoccurence(int[] nums,int x){
  6. int n=nums.length;
  7.  
  8. int low=0;
  9. int high=n-1;
  10.  
  11. int res=-1;
  12. while(low<=high){
  13. int midd=(low+high)/2;
  14. if(nums[midd] < x){
  15. low=midd+1;
  16. }
  17. else if(nums[midd] ==x){
  18. res=midd;
  19. high=midd-1;
  20. }
  21. else{
  22. high=midd-1;
  23. }
  24. }
  25.  
  26. return res;
  27. }
  28. public static int lastoccurence(int[] nums,int x){
  29. int n=nums.length;
  30.  
  31. int low=0;
  32. int high=n-1;
  33.  
  34. int res=-1;
  35. while(low<=high){
  36. int midd=(low+high)/2;
  37. if(nums[midd] < x){
  38. low=midd+1;
  39. }
  40. else if(nums[midd] ==x){
  41. res=midd;
  42. low=midd+1;
  43. }
  44. else{
  45. high=midd-1;
  46. }
  47. }
  48.  
  49. return res;
  50. }
  51. public static void main(String[] args) {
  52. Scanner sc = new Scanner(System.in);
  53. int n=sc.nextInt();
  54. int[]nums = new int[n]; //sorted array given
  55.  
  56. for(int i=0;i<n;i++){
  57. nums[i]=sc.nextInt();
  58. }
  59. int k=sc.nextInt();
  60.  
  61. int low=0;
  62. int high =n-1;
  63.  
  64. while(low<=high){
  65. int mid = (low+high)/2;
  66.  
  67. int l1= firstoccurence(nums,nums[mid]);
  68. int h1= lastoccurence(nums,nums[mid]);
  69.  
  70. if((h1-l1+1) <k){
  71. System.out.print("Required element is :" + nums[mid]);
  72. break;
  73. }
  74. else{
  75. if((h1-low+1)%k ==0 ){ //means no problem till h1 index
  76. low=h1+1;
  77. }
  78. else if((h1-low+1)%k !=0 ){ //problem is within low...l1
  79.  
  80. high=l1-1;
  81. }
  82.  
  83. }
  84.  
  85.  
  86. }
  87. }
  88. }
Runtime error #stdin #stdout #stderr 0.14s 17624KB
stdin
Standard input is empty
stdout
Standard output is empty
stderr
Exception in thread "main" java.util.NoSuchElementException
	at java.base/java.util.Scanner.throwFor(Scanner.java:937)
	at java.base/java.util.Scanner.next(Scanner.java:1594)
	at java.base/java.util.Scanner.nextInt(Scanner.java:2258)
	at java.base/java.util.Scanner.nextInt(Scanner.java:2212)
	at Main.main(Main.java:53)