Рубрики

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

Дан массив arr [] длины N. Задача состоит в том, чтобы проверить, существует ли какой-либо подмассив, сумма которого кратна N. Если такой подмассив существует, выведите начальный и конечный индекс этого подмассива, иначе выведите -1 . Если таких подмассивов несколько, выведите любой из них.

Примеры:

Input: arr[] = {7, 5, 3, 7}
Output: 0 1
Sub-array from index 0 to 1 is [7, 5]
sum of this subarray is 12 which is a multiple of 4

Input: arr[] = {3, 7, 14}
Output: 0 0

Наивный подход . Наивный подход заключается в создании всех подмассивов и вычислении их суммы. Если сумма для любого подмассива кратна N, верните начальный и конечный индексы.

Сложность времени: O (N 3 )

Лучший подход: лучший подход заключается в поддержании массива префиксных сумм, в котором хранится сумма всех предыдущих элементов. Чтобы вычислить сумму подмассива между индексами i и j, мы можем использовать формулу:

subarray sum[i:j] = presum[j]-presum[i-1]

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

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация вышеуказанного подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция для поиска подмассива
// чья сумма кратна N

void CheckSubarray(int arr[], int N)

{

  

    // Префиксный массив для хранения накопленной суммы

    int presum[N + 1] = { 0 };

  

    // Динамическое программирование одного состояния

    // отношение для массива префиксных сумм

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

  

        presum[i] = presum[i - 1] + arr[i - 1];

    }

  

    // Генерация всех подмассивов

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

  

        for (int j = i; j <= N; j += 1) {

  

            // Если сумма подмассива [i: j]

            // кратно N

            if ((presum[j] - presum[i - 1]) % N == 0) {

                cout << i - 1 << " " << j - 1;

                return;

            }

        }

    }

  

    // Если функция достигает здесь, значит

    // нет подмассивов с суммой

    // как кратное N

    cout << -1;

}

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

int main()

{

    int arr[] = { 7, 5, 3, 7 };

  

    int N = sizeof(arr) / sizeof(arr[0]);

  

    CheckSubarray(arr, N);

  

    return 0;

}

Джава

// Java реализация вышеупомянутого подхода

import java.io.*;

  

class GFG 

{

  
// Функция для поиска подмассива
// чья сумма кратна N

static void CheckSubarray(int arr[], int N)

{

  

    // Префиксный массив для хранения накопленной суммы

    int presum[] = new int[N + 1];

  

    // Динамическое программирование одного состояния

    // отношение для массива префиксных сумм

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

    {

  

        presum[i] = presum[i - 1] + arr[i - 1];

    }

  

    // Генерация всех подмассивов

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

    {

  

        for (int j = i; j <= N; j += 1

        {

  

            // Если сумма подмассива [i: j]

            // кратно N

            if ((presum[j] - presum[i - 1]) % N == 0)

            {

                System.out.print((i - 1) + " " + (j - 1));

                return;

            }

        }

    }

  

    // Если функция достигает здесь, значит

    // нет подмассивов с суммой

    // как кратное N

    System.out.print(-1);

}

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

public static void main (String[] args)

{

    int []arr = { 7, 5, 3, 7 };

  

    int N = arr.length;

  

    CheckSubarray(arr, N);

  
}
}

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

python3

# Python3 реализация вышеуказанного подхода

  
# Функция для поиска подмассива
# чья сумма кратна N

def CheckSubarray(arr, N):

  

    # Префиксный массив массивов для хранения накопленной суммы

    presum=[0 for i in range(N + 1)]

  

    # Динамическое программирование одного состояния

    # отношение для массива префиксных сумм

    for i in range(1, N+1):

        presum[i] = presum[i - 1] + arr[i - 1]

  

    # Генерация всех подмассивов

    for i in range(1, N+1):

  

        for j in range(i, N+1):

  

            # Если сумма подмассива [i: j]

            # кратно N

            if ((presum[j] - presum[i - 1]) % N == 0):

                print(i - 1,j - 1)

                return

  

  

    # Если функция достигает здесь, значит

    # нет подмассивов с суммой

    # как кратное N

    print("-1")

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

  

arr = [ 7, 5, 3, 7]

  

N = len(arr)

  
CheckSubarray(arr, N)

  
# Этот код предоставлен mohit kumar 29

C #

// C # реализация вышеуказанного подхода

using System;

  

class GFG 

{

  
// Функция для поиска подмассива
// чья сумма кратна N

static void CheckSubarray(int []arr, int N)

{

  

    // Префиксный массив для хранения накопленной суммы

    int []presum = new int[N + 1];

  

    // Динамическое программирование одного состояния

    // отношение для массива префиксных сумм

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

    {

  

        presum[i] = presum[i - 1] + arr[i - 1];

    }

  

    // Генерация всех подмассивов

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

    {

  

        for (int j = i; j <= N; j += 1) 

        {

  

            // Если сумма подмассива [i: j]

            // кратно N

            if ((presum[j] - presum[i - 1]) % N == 0)

            {

                Console.Write((i - 1) + " " + (j - 1));

                return;

            }

        }

    }

  

    // Если функция достигает здесь, значит

    // нет подмассивов с суммой

    // как кратное N

    Console.Write(-1);

}

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

public static void Main ()

{

    int []arr = { 7, 5, 3, 7 };

  

    int N = arr.Length;

  

    CheckSubarray(arr, N);

  
}
}

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

Выход:

0 1

Сложность времени: O (N 2 )

Эффективный подход: идея заключается в использовании принципа голубиных отверстий. Давайте предположим, что элементами массива являются 1 , a 2 … a N.
Для последовательности чисел следующим образом:

a1, a1 + a2, a1 + a2 + a3, …, a1 + a2 +a3 + … +aN

В приведенной последовательности есть N терминов. Возможны два случая:

  1. Если одна из вышеприведенных сумм префиксов кратна N, выведите i- й индекс подмассива.
  2. Если ни один из перечисленных выше элементов последовательности не лежит в 0 по модулю класса N , то остается (N — 1) по модулю классов. По принципу « голубиная дыра» существует N голубей (элементы последовательности сумм префиксов) и (N — 1) дырок (классы по модулю), можно сказать, что как минимум два элемента будут лежать в одном классе по модулю. Разница между этими двумя элементами даст подмассив, сумма которого будет кратна N.

Видно, что такой подмассив всегда можно получить.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация вышеуказанного подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция для проверки, существует ли
// подмассив, сумма которого кратна N

void CheckSubarray(int arr[], int N)

{

  

    // Префиксный массив для хранения накопленной суммы

    int presum[N + 1] = { 0 };

  

    // Динамическое программирование одного состояния

    // отношение для массива префиксных сумм

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

  

        presum[i] = presum[i - 1] + arr[i - 1];

    }

  

    // вектор по модулю

    vector<int> moduloclass[N];

  

    // Сохраняем значение индекса в векторе по модулю

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

        moduloclass[presum[i] % N].push_back(i - 1);

    }

  

    // Если существует подмассив с

    // начальный индекс равен нулю

    if (moduloclass[0].size() > 0) {

        cout << 0 << " " << moduloclass[0][0];

        return;

    }

  

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

  

        // В этом классе более двух презумпций% N

        // Следовательно, разница любых двух подмассивов будет

        // кратно N

        if (moduloclass[i].size() >= 2) {

  

            // 0 на основе индексации

            cout << moduloclass[i][0] + 1 << " " << moduloclass[i][1];

            return;

        }

    }

}

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

int main()

{

    int arr[] = { 7, 3, 5, 2 };

  

    int N = sizeof(arr) / sizeof(arr[0]);

  

    CheckSubarray(arr, N);

  

    return 0;

}

Джава

// Java реализация вышеупомянутого подхода

import java.util.*;

  

class GFG

{

  
// Функция для проверки, существует ли
// подмассив, сумма которого кратна N

static void CheckSubarray(int arr[], int N) 

{

  

    // Префиксный массив для хранения накопленной суммы

    int[] presum = new int[N + 1];

  

    // Динамическое программирование одного состояния

    // отношение для массива префиксных сумм

    for (int i = 1; i <= N; i += 1

    {

        presum[i] = presum[i - 1] + arr[i - 1];

    }

  

    // вектор по модулю

    Vector<Integer>[] moduloclass = new Vector[N];

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

    {

        moduloclass[i] = new Vector<>();

    }

  

    // Сохраняем значение индекса

    // в векторе по модулю

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

    {

        moduloclass[presum[i] % N].add(i - 1);

    }

  

    // Если существует подмассив с

    // начальный индекс равен нулю

    if (moduloclass[0].size() > 0)

    {

        System.out.print(0 + " "

               moduloclass[0].get(0));

        return;

    }

  

    for (int i = 1; i < N; i += 1

    {

  

        // В этом классе более

        // две презумпции% N. Отсюда разница

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

        if (moduloclass[i].size() >= 2

        {

  

            // 0 на основе индексации

            System.out.print(moduloclass[i].get(0) + 1 +

                       " " + moduloclass[i].get(1));

            return;

        }

    }

}

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

public static void main(String args[]) 

{

    int arr[] = {7, 3, 5, 2};

  

    int N = arr.length;

  

    CheckSubarray(arr, N);

}                     
}

  
// Этот код предоставлен 29AjayKumar

python3

# Python 3 реализация вышеуказанного подхода

  
# Функция для проверки, существует ли
# подмассив, сумма которого кратна N

def CheckSubarray(arr, N):

    # Префиксный массив массивов для хранения накопленной суммы

    presum = [0 for i in range(N+1)]

  

    # Динамическое программирование одного состояния

    # отношение для массива префиксных сумм

    for i in range(1,N+1):

        presum[i] = presum[i - 1] + arr[i - 1]

  

    # Модуль класса вектор

    moduloclass = [[]]*N

  

    # Сохранение значения индекса в векторе класса по модулю

    for i in range(1,N+1,1):

        moduloclass[presum[i] % N].append(i - 1)

  

    # Если существует подмассив с

    # начальный индекс равен нулю

    if (len(moduloclass[0]) > 0):

        print(0+1,moduloclass[0][0]+2)

        return

  

    for i in range(1,N):

        # В этом классе более двух презумпций% N

        # Следовательно, разница любых двух подмассивов будет

        # кратное N

        if (len(moduloclass[i]) >= 2):

            Индексирование на основе # 0

            print(moduloclass[i][0] + 1,moduloclass[i][1])

            return

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

if __name__ == '__main__':

    arr = [7, 3, 5, 2]

  

    N = len(arr)

  

    CheckSubarray(arr, N)

  
# Этот код предоставлен
# Surendra_Gangwar

C #

// C # реализация подхода

using System;

using System.Collections.Generic; 

  

class GFG

{

  
// Функция для проверки, существует ли
// подмассив, сумма которого кратна N

static void CheckSubarray(int []arr, int N) 

{

  

    // Префиксный массив для хранения накопленной суммы

    int[] presum = new int[N + 1];

  

    // Динамическое программирование одного состояния

    // отношение для массива префиксных сумм

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

    {

        presum[i] = presum[i - 1] + arr[i - 1];

    }

  

    // вектор по модулю

    List<int>[] moduloclass = new List<int>[N];

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

    {

        moduloclass[i] = new List<int>();

    }

  

    // Сохраняем значение индекса

    // в векторе по модулю

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

    {

        moduloclass[presum[i] % N].Add(i - 1);

    }

  

    // Если существует подмассив с

    // начальный индекс равен нулю

    if (moduloclass[0].Count > 0)

    {

        Console.Write(0 + " "

            moduloclass[0][0]);

        return;

    }

  

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

    {

  

        // В этом классе более

        // две презумпции% N. Отсюда разница

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

        if (moduloclass[i].Count >= 2) 

        {

  

            // 0 на основе индексации

            Console.Write(moduloclass[i][0] + 1 +

                    " " + moduloclass[i][1]);

            return;

        }

    }

}

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

public static void Main(String []args) 

{

    int []arr = {7, 3, 5, 2};

  

    int N = arr.Length;

  

    CheckSubarray(arr, N);

}                     
}

  
// Этот код предоставлен Rajput-Ji

Выход:

1 2

Сложность времени: O (N)

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

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

0.00 (0%) 0 votes