fork download
copy 
  1. class Main {
  2.  
  3.     // Method to find the first occurrence of 'value' in array 'b'
  4.     public static int firstOccurrence(int value, int[] b, int n) {
  5.         int start = 0, end = n - 1;
  6.         while (start <= end) {
  7.             int mid = start + (end - start) / 2;
  8.             if (b[mid] == value) {
  9.                 if (mid == 0 || b[mid - 1] != value) {
  10.                     return mid; // Found the first occurrence
  11.                 } else {
  12.                     end = mid - 1; // Search in the left half
  13.                 }
  14.             } else if (b[mid] < value) {
  15.                 start = mid + 1; // Search in the right half
  16.             } else {
  17.                 end = mid - 1; // Search in the left half
  18.             }
  19.         }
  20.         return -1; // Not found
  21.     }
  22.  
  23.     // Method to find the last occurrence of 'value' in array 'b'
  24.     public static int lastOccurrence(int value, int[] b, int n) {
  25.         int start = 0, end = n - 1;
  26.         while (start <= end) {
  27.             int mid = start + (end - start) / 2;
  28.             if (b[mid] == value) {
  29.                 if (mid == n - 1 || b[mid + 1] != value) {
  30.                     return mid; // Found the last occurrence
  31.                 } else {
  32.                     start = mid + 1; // Search in the right half
  33.                 }
  34.             } else if (b[mid] < value) {
  35.                 start = mid + 1; // Search in the right half
  36.             } else {
  37.                 end = mid - 1; // Search in the left half
  38.             }
  39.         }
  40.         return -1; // Not found
  41.     }
  42.  
  43.     // Method to find an element that does not occur exactly k times
  44.     public static int findElement(int[] b, int n, int k) {
  45.         int low = 0;
  46.         int high = n - 1;
  47.  
  48.         while (low <= high) {
  49.             int mid = (low + high) / 2;
  50.  
  51.             int l1 = firstOccurrence(b[mid], b, n);
  52.             int h1 = lastOccurrence(b[mid], b, n);
  53.  
  54.             int d = (l1 != -1 && h1 != -1) ? (h1 - l1 + 1) : 0; // Check for valid indices
  55.  
  56.             if (d < k) { // If occurrences are less than k
  57.                 return b[mid];
  58.             }
  59.  
  60.             if ((h1 - low + 1) % k == 0) { // Check if the range is valid
  61.                 low = h1 + 1; // Move to the right
  62.             } else {
  63.                 high = l1 - 1; // Move to the left
  64.             }
  65.         }
  66.  
  67.         return -1; // Return -1 if no valid element is found
  68.     }
  69.  
  70.     public static void main(String[] args) {
  71.         int[] b = {1, 2, 2, 3, 3, 3, 4, 4, 4, 4}; // Example array
  72.         int n = b.length;
  73.         int k = 3; // Example k value
  74.         int result = findElement(b, n, k);
  75.  
  76.         if (result != -1) {
  77.             System.out.println("Element that does not occur " + k + " times: " + result);
  78.         } else {
  79.             System.out.println("All elements occur " + k + " times or more.");
  80.         }
  81.     }
  82. }
  83.  
Success #stdin #stdout 0.14s 57356KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
All elements occur 3 times or more.
https://ideone.com/LgByGk
language:
Java (HotSpot 12)
created:
13 hours 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!