fork download
copy 
  1.  
  2. import java.util.*;
  3.  
  4. public class Main {
  5.  
  6.     public static int solve(int[] pgcd, int[] sgcd, int skip, int[] nums) {
  7.         int n = nums.length;
  8.  
  9.         // Prefix GCD
  10.         for (int i = 1; i <= n; i++) {
  11.             if (i - 1 == skip) {
  12.                 pgcd[i] = pgcd[i - 1];
  13.                 continue;
  14.             }
  15.  
  16.             pgcd[i] = gcd(pgcd[i - 1], nums[i - 1]);
  17.         }
  18.  
  19.         // Suffix GCD
  20.         for (int i = n - 1; i >= 0; i--) {
  21.             if (i == skip) {
  22.                 sgcd[i] = sgcd[i + 1];
  23.                 continue;
  24.             }
  25.  
  26.             sgcd[i] = gcd(sgcd[i + 1], nums[i]);
  27.         }
  28.  
  29.         int score = 0;
  30.  
  31.         for (int i = 0; i < n - 1; i++) {
  32.             if (i == skip) continue;
  33.  
  34.             if (pgcd[i + 1] == sgcd[i + 1]) {
  35.                 score++;
  36.             }
  37.         }
  38.  
  39.         return score;
  40.     }
  41.  
  42.     public static int gcd(int a, int b) {
  43.         while (b != 0) {
  44.             int temp = b;
  45.             b = a % b;
  46.             a = temp;
  47.         }
  48.         return a;
  49.     }
  50.  
  51.     public static int maxValidSplits(int[] nums) {
  52.         int n = nums.length;
  53.         int ans = 0;
  54.  
  55.         int[] premain = new int[n + 1];
  56.  
  57.         for (int i = 1; i <= n; i++) {
  58.             premain[i] = gcd(premain[i - 1], nums[i - 1]);
  59.         }
  60.  
  61.         // skip = -1 means no deletion
  62.         for (int i = 0; i <= n; i++) {
  63.  
  64.             if (i > 0 && premain[i] == premain[i - 1]) {
  65.                 continue;
  66.             }
  67.  
  68.             int skip = i - 1;
  69.  
  70.             int[] pgcd = new int[n + 1];
  71.             int[] sgcd = new int[n + 1];
  72.  
  73.             ans = Math.max(
  74.                 ans,
  75.                 solve(pgcd, sgcd, skip, nums)
  76.             );
  77.         }
  78.  
  79.         return ans;
  80.     }
  81.  
  82.     public static void main(String[] args) {
  83.  
  84.         // Example 1
  85.         int[] nums1 = {10, 30, 15, 10};
  86.         System.out.println(maxValidSplits(nums1)); // 2
  87.  
  88.         // Example 2
  89.         int[] nums2 = {2, 10, 14};
  90.         System.out.println(maxValidSplits(nums2)); // 1
  91.  
  92.         // Example 3
  93.         int[] nums3 = {2, 4};
  94.         System.out.println(maxValidSplits(nums3)); // 0
  95.     }
  96. }
  97.  
Success #stdin #stdout 0.08s 44280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2
1
0
https://ideone.com/kv0aJm
language:
Java (HotSpot 12)
created:
1 day 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!