Рубрики

Наименьший подмассив, сумма которого кратна размеру массива

Для массива размером N нам нужно найти подмассив наименьшего размера, сумма которого делится на размер массива N.

Примеры :

Input  : arr[] = [1, 1, 2, 2, 4, 2]    
Output : [2 4]
Size of array, N = 6    
Following subarrays have sum as multiple of N
[1, 1, 2, 2], [2, 4], [1, 1, 2, 2, 4, 2]
The smallest among all is [2 4]

Мы можем решить эту проблему, учитывая следующие факты,

Let S[i] denotes sum of first i elements i.e.  
   S[i] = a[1] + a[2] .. + a[i]
Now subarray arr(i, i + x) has sum multiple of N then,
  (arr(i] + arr[i+1] + .... + arr[i + x])) % N = 0
  (S[i+x] – S[i] ) % N  = 0
  S[i] % N = S[i + x] % N 

Нам нужно найти минимальное значение x, для которого выполняется указанное выше условие. Это может быть реализовано за одну итерацию с O (N) сложностью по времени с использованием другого массива modIdx размера N. Массив modIdx инициализируется со всеми элементами как -1. modIdx [k] должен обновляться с i на каждой итерации, где k = сумма% N.
Теперь в каждой итерации нам нужно обновлять modIdx [k] в соответствии со значением суммы% N.

Нам нужно проверить две вещи,
Если в любой момент времени k = 0, и мы впервые обновляем modIdx [0] (то есть modIdx [0] был -1)
Затем мы присваиваем x i + 1, потому что (i + 1) будет длиной подмассива, сумма которого кратна N
В другом случае всякий раз, когда мы получаем значение мода, если этот индекс не равен -1, это означает, что он обновляется каким-либо другим значением суммы, чей индекс хранится в этом индексе, мы обновляем x с этим значением разницы, то есть i — modIdx. [к] .
После каждой вышеуказанной операции мы обновляем минимальное значение длины и соответствующий начальный индекс и конечный индекс для подмассива. Наконец, это дает решение нашей проблемы.

C ++

// C ++ программа для поиска подмассива, чья сумма
// кратен размеру
#include <bits/stdc++.h>

using namespace std;

  
// Метод печатает наименьший подмассив с суммой
// кратно размеру

void printSubarrayMultipleOfN(int arr[], int N)

{

    // Таблица прямого индекса, чтобы увидеть, если сумма% N

    // появился раньше или нет.

    int modIdx[N]; 

  

    // инициализируем весь индекс мода с -1

    for (int i = 0; i < N; i++)

        modIdx[i] = -1;

  

    // инициализация minLen и curLen большим

    // ценности

    int minLen = N + 1;

    int curLen = N + 1;

  

    // Для хранения суммы элементов массива

    int sum = 0;

  

    // цикл для каждого значения массива

    int l, r;

    for (int i = 0; i < N; i++)

    {

        sum += arr[i];

        sum %= N;

  

        // Если это первый раз, когда мы имеем

        // получил значение мода как 0, затем S (0, i)% N

        // == 0

        if (modIdx[sum] == -1 && sum == 0)

            curLen = i + 1;

  

        // Если мы достигли этого мода раньше

        // длина подмассива будет i - предыдущая_позиция

        if (modIdx[sum] != -1)

            curLen = i - modIdx[sum];

  

        // выбираем минимальную длину подрешетки до сих пор

        if (curLen < minLen)

        {

            minLen = curLen;

  

            // обновляем левый и правый индексы подмассива

            l = modIdx[sum] + 1;

            r = i;

        }

        modIdx[sum] = i;

    }

  

    // печать подмассива

    for (int i = l; i <= r; i++)

        cout << arr[i] << " ";

    cout << endl;

}

  
// Код драйвера для проверки вышеуказанного метода

int main()

{

    int arr[] = {1, 1, 2, 2, 4, 2};

    int N = sizeof(arr) / sizeof(int);

  

    printSubarrayMultipleOfN(arr, N);

    return 0;

}

Джава

// Java-программа для поиска подмассива, чья сумма
// кратен размеру

class GFG {

      

    // Метод печатает наименьший подмассив с суммой

    // кратно размеру

    static void printSubarrayMultipleOfN(int arr[], 

                                              int N)

    {

          

        // Таблица прямого индекса, чтобы увидеть, если сумма% N

        // появился раньше или нет.

        int modIdx[] = new int[N];

  

        // инициализируем весь индекс мода с -1

        for (int i = 0; i < N; i++)

            modIdx[i] = -1;

  

        // инициализируем minLen и curLen с помощью

        // большие значения

        int minLen = N + 1;

        int curLen = N + 1;

  

        // Для хранения суммы элементов массива

        int sum = 0;

  

        // цикл для каждого значения массива

        int l = 0, r = 0;

          

        for (int i = 0; i < N; i++) {

            sum += arr[i];

            sum %= N;

  

            // Если мы впервые

            // получим значение мода как 0, тогда

            // S (0, i)% N == 0

            if (modIdx[sum] == -1 && sum == 0)

                curLen = i + 1;

  

            // Если мы достигли этого мода раньше

            // тогда длина подмассива будет равна

            // - Предыдущая позиция

            if (modIdx[sum] != -1)

                curLen = i - modIdx[sum];

  

            // выбираем минимальную длину os subarray

            // до сих пор

            if (curLen < minLen) {

                minLen = curLen;

  

                // обновляем левый и правый индексы

                // подмассива

                l = modIdx[sum] + 1;

                r = i;

            }

              

            modIdx[sum] = i;

        }

  

        // печать подмассива

        for (int i = l; i <= r; i++)

            System.out.print(arr[i] + " ");

              

        System.out.println();

    }

      

    // Драйвер программы

    public static void main(String arg[])

    {

        int arr[] = { 1, 1, 2, 2, 4, 2 };

        int N = arr.length;

  

        printSubarrayMultipleOfN(arr, N);

    }

}

  
// Этот код предоставлен Anant Agarwal.

python3

# Python3 программа для поиска подмассива
# чья сумма кратна размеру

  
# Метод печатает наименьший подмассив
# чья сумма кратна размеру

def printSubarrayMultipleOfN(arr, N):

  

    # Таблица прямого индекса, чтобы увидеть, если сумма% N

    # появился раньше или нет.

    modIdx = [0 for i in range(N)] 

  

    # инициализировать весь индекс мода с -1

    for i in range(N):

        modIdx[i] = -1

  

    # инициализация minLen и curLen

    # с большими значениями

    minLen = N + 1

    curLen = N + 1

  

    # Хранить сумму элементов массива

    sum = 0

  

    # цикл для каждого значения массива

    l = 0; r = 0

    for i in range(N):

      

        sum += arr[i]

        sum %= N

  

        # Если мы впервые

        # получил значение мода как 0, затем S (0, i)% N

        # == 0

        if (modIdx[sum] == -1 and sum == 0):

            curLen = i + 1

  

        # Если мы дошли до этого мода до этого

        # длина подмассива будет i - предыдущая_позиция

        if (modIdx[sum] != -1):

            curLen = i - modIdx[sum]

  

        # выберите минимальную длину подрешетки до сих пор

        if (curLen < minLen):

          

            minLen = curLen

  

            # обновить левый и правый индексы подмассива

            l = modIdx[sum] + 1

            r = i

          

        modIdx[sum] = i

      

    # print subarray

    for i in range(l, r + 1):

        print(arr[i] , " ", end = "")

    print()

  
# Драйверная программа

arr = [1, 1, 2, 2, 4, 2]

N = len(arr)

printSubarrayMultipleOfN(arr, N)

  
# Этот код предоставлен Anant Agarwal.

C #

// C # программа для поиска подмассива, чья сумма
// кратен размеру

using System;

class GFG {

      

    // Метод печатает наименьший подмассив с суммой

    // кратно размеру

    static void printSubarrayMultipleOfN(int []arr, 

                                            int N)

    {

          

        // Таблица прямого индекса, чтобы увидеть, если сумма% N

        // появился раньше или нет.

        int []modIdx = new int[N];

  

        // инициализируем весь индекс мода с -1

        for (int i = 0; i < N; i++)

            modIdx[i] = -1;

  

        // инициализируем minLen и curLen с помощью

        // большие значения

        int minLen = N + 1;

        int curLen = N + 1;

  

        // Для хранения суммы элементов массива

        int sum = 0;

  

        // цикл для каждого значения массива

        int l = 0, r = 0;

          

        for (int i = 0; i < N; i++) {

            sum += arr[i];

            sum %= N;

  

            // Если мы впервые

            // получим значение мода как 0, тогда

            // S (0, i)% N == 0

            if (modIdx[sum] == -1 && sum == 0)

                curLen = i + 1;

  

            // Если мы достигли этого мода раньше

            // тогда длина подмассива будет равна

            // - Предыдущая позиция

            if (modIdx[sum] != -1)

                curLen = i - modIdx[sum];

  

            // выбираем минимальную длину os subarray

            // до сих пор

            if (curLen < minLen) {

                minLen = curLen;

  

                // обновляем левый и правый индексы

                // подмассива

                l = modIdx[sum] + 1;

                r = i;

            }

              

            modIdx[sum] = i;

        }

  

        // печать подмассива

        for (int i = l; i <= r; i++)

            Console.Write(arr[i] + " ");

              

        Console.WriteLine();

    }

      

    // Код драйвера

    public static void Main()

    {

        int []arr = {1, 1, 2, 2, 4, 2};

        int N = arr.Length;

  

        printSubarrayMultipleOfN(arr, N);

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// PHP программа для поиска подмассива
// чья сумма кратна размеру

  
// Метод печатает наименьший подмассив
// чья сумма кратна размеру

function printSubarrayMultipleOfN($arr

                                  $N)

{

    // Таблица прямого индекса, чтобы увидеть

    // если появилась сумма% N

    // до или нет.

    $modIdx = array(); 

  

    // инициализируем весь мод

    // индекс с -1

    for ($i = 0; $i < $N; $i++)

        $modIdx[$i] = -1;

  

    // инициализируем minLen и

    // curLen с большими значениями

    $minLen = $N + 1;

    $curLen = $N + 1;

  

    // Для хранения суммы

    // элементы массива

    $sum = 0;

  

    // цикл для каждого

    // значение массива

    $l; $r;

    for ($i = 0; $i < $N; $i++)

    {

        $sum += $arr[$i];

        $sum %= $N;

  

        // Если это первый раз

        // мы получили значение мода как 0,

        // тогда S (0, i)% N == 0

        if ($modIdx[$sum] == -1 && 

            $sum == 0)

            $curLen = $i + 1;

  

        // Если мы достигли этого мода

        // до длины потомка

        // буду я - предыдущая_позиция

        if ($modIdx[$sum] != -1)

            $curLen = $i - $modIdx[$sum];

  

        // выбираем минимальную длину

        // как подрешетка до сих пор

        if ($curLen < $minLen)

        {

            $minLen = $curLen;

  

            // обновить влево и вправо

            // индексы подмассива

            $l = $modIdx[$sum] + 1;

            $r = $i;

        }

        $modIdx[$sum] = $i;

    }

  

    // печать подмассива

    for ($i = $l; $i <= $r; $i++)

        echo $arr[$i] , " ";

    echo "\n" ;

}

  
// Код драйвера

$arr = array(1, 1, 2, 2, 4, 2);

$N = count($arr);

  

printSubarrayMultipleOfN($arr, $N);

  
// Этот код предоставлен anuj_67.
?>


Выход :

2 4

Эта статья предоставлена Уткаршем Триведи . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Наименьший подмассив, сумма которого кратна размеру массива

0.00 (0%) 0 votes