Количество непрерывных сегментов?

Question

Массив A из N целых чисел и целое число K. Подсчитайте количество непустых смежных подпоследовательностей A, так что в этом субсегменте нет плохих пар целых чисел. Пара (x, y) целых чисел называется плохим, если x находится слева от y в массиве и x mod y = K?

Любая идея лучше в или в тета (n^2). Моя испытанная идея -
Одним из решений является сохранение (на карте) такого количества пар (в O (n^2)), а затем просто перебирать все подсегменты, чтобы дополнительно проверить, присутствуют ли эти пары или нет в этом сегменте это ...

Подпоследовательность означает: - Если массив имеет N элементов, чем у N * (N + 1)/2 подпоследовательностей, т.е. 9,8,7,6,5, то имеем [9]; [8 ]; [7]; [6]; [5]; [9,8]; [8,7]; [7,6]; [6,5]; [9,8,7]; [8,7 , 6], [7,6,5], [9,8,7,6], [8, 7,6,5], [9,8,7,6,5] - все подпоследовательности :) -

Answer 1

check this solution 

    #include <iostream> 
    using namespace std; 

    int main() 
    { 
    int n,k; 
    cin>>n>>k; 
    int a[n+1],i,j,ans=0; 
    for(i=1;i<=n;i++) 
cin>>a[i]; 
for(i=1;i<=n;i++){ 
    for(j=i+1;j<=n;j++){ 
     if(a[i]%a[j]==k){ 
      ans=ans+(n-j+1); 
break; 
     } 
    } 
} 
    //if(k==0)ans=ans+n; 
    cout<<n*(n+1)/2-ans; 
// your code goes here 
    return 0; 
    } 

Answer 2

Здесь вы найдете решение, написанное в Swift O (n).

Основная идея состоит в том, чтобы найти индексы всех плохих пар в основной последовательности, а затем рассчитать количество подпоследовательностей между этими индексами с вашей формулой (разделение плохих пар).

императива подход:

func numberOfSubsequences(array: [Int], k: Int) -> Int { 
    // some spacial cases where you can return immediately 
    if array.count <= 1 { return array.count } 
    if array.count == 2 { return array[0] % array[1] == k ? 2 : 3 } 

    var numberOfSubsequences = 0 
    var startOfSubsequence = 0 
    for i in 0..<array.count - 1 { 
     // if a bad pair is found calculate the subsequence count between startOfSubsequence and i 
     if array[i] % array[i+1] == k { 
      let sequenceLength = i - startOfSubsequence + 1 
      numberOfSubsequences += sequenceLength * (sequenceLength+1)/2 
      startOfSubsequence = i + 1 
     } 
    } 
    // adding the remaining subsequence count from startOfSubsequence to the end of the array 
    return numberOfSubsequences + (array.count - startOfSubsequence)*(array.count - startOfSubsequence + 1)/2 
} 

а (больше) функциональный подхода с использованием хвостовой рекурсии:

func numberOfSubsequences2(array: [Int], k: Int) -> Int { 
    if array.count <= 1 { return array.count } 
    if array.count == 2 { return array[0] % array[1] == k ? 2 : 3 } 

    // find first index of a bad pair 
    var i = 0 
    while (i + 1 < array.count) && (array[i] % array[i+1] != k) { 
     i++ 
    } 
    let count = (i+1)*(i+2)/2 

    // recurse over the remaining array (tail) from i+1 to the end 
    let tail = Array(array[i+1..<array.count]) 
    return count + numberOfSubsequences2(tail, k: k) 
}