Как найти сумму индексов элементов массива

Usually, we require to find the sum of index, in which the particular value is located. There are many method to achieve that, using index() etc. But sometimes require to find all the indices of a particular value in case it has multiple occurrences in list. Lets discuss certain ways to do so.

Method #1 : Naive Method + sum() We can achieve this task by iterating through the list and check for that value and just append the value index in new list and print that. This is the basic brute force method to achieve this task. The sum() is used to perform sum of list. 

Original list : [1, 3, 4, 3, 6, 7]
New indices summation : 4

Time complexity: O(n) where n is the length of the test_list. The code uses a for loop to traverse the list and perform the necessary operation
Auxiliary space: O(m), where m is the number of occurrences of the element being searched in the list. This is because the space complexity is determined by the size of the res_list, which grows as the number of occurrences of the element being searched increases.

Method #2: Using list comprehension + sum() List comprehension is just the shorthand technique to achieve the brute force task, just uses lesser lines of codes to achieve the task and hence saves programmers time. The sum() is used to perform sum of list. 

Original list : [1, 3, 4, 3, 6, 7]
New indices summation : 4

Time complexity: O(n), where n is the length of the input list ‘test_list’, because the program loops over the input list once to find the indices of the elements equal to 3, and the length of the list is n.
Auxiliary space: O(m), where m is the number of indices where the element is 3. This is because the program creates a new list ‘res_list’ containing these indices, and the size of this list is proportional to the number of occurrences of the element 3 in the input list.

Method#3: Using reduce and lambda function With these function we can perform this task. We can use reduce to iterate over the list range and with lambda function checks if element is define value or not if then we add result with index of element else leave result. 

Output:

Original list : [1, 3, 4, 3, 6, 7]
New indices summation : 4

Time Complexity: O(n), where n is the length of the list test_list 
Auxiliary space: O(m), where m is the number of indices

Method #4: Using for loop, without sum()

Original list : [1, 3, 4, 3, 6, 7]
New indices summation : 4

Method 5: Using numpy

• Convert the list to a numpy array:
  The first step is to convert the original list to a numpy array using the np.array() function. This allows us to use numpy functions to manipulate the data.
• Use the where() function to find the indices of the element:
  Next, we use the np.where() function to find the indices where the target element (in this case, 3) occurs in the numpy array. The where() function returns a tuple of arrays, one for each dimension of the input array. Since we’re working with a 1-dimensional array, we only need the first element of the tuple, which contains the indices.
• Sum the indices:
  We then use the np.sum() function to sum the indices where the element occurs. This gives us the desired result.

Output:

Original list: [1, 3, 4, 3, 6, 7]
New indices summation: 4

Time Complexity: O(n + m)

• Converting the list to a numpy array takes O(n) time, where n is the length of the list.
• The np.where() function takes O(n) time to find the indices where the target element occurs in the numpy array.
• The np.sum() function takes O(m) time to sum the indices, where m is the number of indices returned by np.where().
• Therefore, the overall time complexity of the numpy approach is O(n + m).

Auxiliary Space: O(n + m)

• Converting the list to a numpy array requires O(n) auxiliary space to store the numpy array.
• The np.where() function returns an array of indices, which requires O(m) auxiliary space to store.
• The np.sum() function requires constant auxiliary space.
• Therefore, the overall auxiliary space complexity of the numpy approach is O(n + m).

Method #6: Using enumerate and for loop, without sum()

Use enumerate and a for loop to iterate over the list and calculate the sum of indices where the element occurs

Original list: [1, 3, 4, 3, 6, 7]
New indices summation: 4

Time complexity: O(n) because it iterates over the entire list once. 
Auxiliary space: O(1) because it only uses a constant amount of extra memory to store the sum of indices.

Method #7: Using itertools:

Algorithm :

1. Initialize the input list test_list with some values.
2. Initialize a variable res to 0.
3. Use the enumerate() function from the itertools module to create an iterator that yields pairs of (index, value) tuples for each element in the list.
4. Use a generator expression with the sum() function to calculate the sum of the indices where the value is equal to 3.
5. Print the sum value res.

Original list: [1, 3, 4, 3, 6, 7]
New indices summation: 4

The time complexity : O(N), where N is the length of the input list. This is because we need to iterate over the entire list once to check each element and its index.

The auxiliary space :O(1), as we are only using a constant amount of extra memory to store the index sum.

Last Updated :
28 Mar, 2023

Like Article

Save Article

Содержание

• 1. Нахождение суммы положительных элементов массива из n целых чисел
  • 1.1. Реализация с помощью цикла for
  • 1.2. Реалізация с помощью цикла while
  • 1.3. Реализация с помощью цикла do…while
• 2. Найти сумму элементов массива, которые размещаются на парных индексах
• 3. Найти произведение элементов массива, которые больше заданного числа
• 4. Определение наличия (отсутствия) заданного символа в массиве символов (тип char)
• 5. Определение наличия (отсутствия) заданного числа в массиве чисел. Массив имеет n целых чисел
• 6. Поиск позиции последнего вхождения элемента k в массиве из n целых чисел
• 7. Поиск позиции первого вхождения элемента k в массиве из n целых чисел
• 8. Подсчет количества элементов k в массиве из n целых чисел
• 9. Подсчет количества элементов в массиве из n вещественных чисел, которые меньше заданного значения k
• 10. Подсчет количества элементов в массиве из n вещественных чисел, значение которых находится в пределах диапазона [a .. b].
• 11. Подсчет количества парных элементов в массиве из n целых чисел
• Связанные темы

Поиск на других ресурсах:

1. Нахождение суммы положительных элементов массива из n целых чисел

Задан массив A из 10 целых чисел. Найти сумму положительных элементов массива

1.1. Реализация с помощью цикла for

В данном примере пропущен ввод массива A

// Нахождение суммы положительных элементов массива
const int MaxN = 10;
int[] A = new int[MaxN]; // заданный массив
int i;

// ввод массива A
// ...

// вычисление суммы
int sum = 0;

for (i=0; i<MaxN; i++)
    if (A[i]>0)
        sum = sum + A[i];

1.2. Реализация с помощью цикла while

// Нахождение суммы положительных элементов массива
const int MaxN = 10;
int[] A = new int[MaxN]; // заданный массив
int i; // дополнительная переменная
int sum = 0; // результат

// ввод массива A
// ...

// вычисление суммы
i=0;
while (i<MaxN)
{
    if (A[i]>0)
        sum+=A[i];
    i++;
}

1.3. Реализация с помощью цикла do…while

// Нахождение суммы положительных элементов массива
const int MaxN = 10;
int[] A = new int[MaxN]; // заданный массив
int i; // дополнительная переменная
int sum = 0; // результат

// ввод массива A
// ...

// вычисление суммы
i=0;

do
{
    if (A[i]>0)
        sum+=A[i];
    i++;
}
while (i<MaxN);

2. Найти сумму элементов массива, которые размещаются на парных индексах

В данном примере вычисляются суммы элементов массива A, индексы которых есть парными: 0, 2, 4, … Чтобы определить есть ли число (индекс массива) парным, нужно выполнить проверку

if ((i%2)==0)
{
    // действия, если число парное
    // ...
}

Реализация решения данной задачи тремя видами цикла (ввод массива A пропущен).

// Нахождение суммы элементов массива, имеющих парные индексы (0, 2, 4,...)
const int MaxN = 10;
int[] A = new int[MaxN]; // заданный массив
int i; // дополнительная переменная
int sum1, sum2, sum3; // результаты вычислений разными видами циклов

// ввод массива A
// ...

// вычисление суммы, цикл for
sum1 = 0;
for (i=0; i<MaxN; i++)
    if ((i%2)==0) // определение парности числа
        sum1+=A[i];

// вычисление суммы, цикл while
sum2 = 0;
i=0;
while (i<MaxN)
{
    if ((i%2)==0) sum2+=A[i];
    i++;
}

// вычисление суммы, цикл do...while
sum3 = 0;
i=0;
do
{
    if ((i%2)==0)
        sum3+=A[i];
    i++;
}
while (i<MaxN);

3. Найти произведение элементов массива, которые больше заданного числа

В примере находится произведение элементов массива A, которые больше числа, которое размещается в переменной number.
Реализация задачи с использованием цикла for:

// произведение элементов массива, которые больше заданного числа
const int MaxN = 10;
int[] A = new int[MaxN]; // заданный массив
int number; // заданное число
int i; // дополнительная переменная
int res; // результат - произведение

// ввод массива A
for (i=0; i<MaxN; i++)
{
    A[i] = i;
}

// задание числа number
number = 5;

// поиск произведения - цикл for
res = 1;
for (i=0; i<MaxN; i++)
    if (A[i]>number)
        res = res * A[i];

// res = 3024

Если размерность массива большая, то результат произведения целесообразно держать в переменной типа double (float). Это связано с тем, что результатом произведения могут быть очень большие или очень маленькие числа. При использовании целых типов может возникнуть переполнение.

Фрагмент реализации данной задачи с использованием цикла while

...

// поиск произведения - цикл while
res = 1;
i=0;
while (i<MaxN)
{
    if (A[i]>number)
        res = res * A[i];
    i++;
}
// res = 3024

Реализация с помощью цикла do…while

// поиск произведения - цикл do...while
res = 1;
i=0;

do
{
    if (A[i]>number)
    res = res * A[i];
        i++;
}
while (i<MaxN);

// res = 3024

4. Определение наличия (отсутствия) заданного символа в массиве символов (тип char)

Пусть задан массив символов M. Определить, есть ли заданный символ sym в массиве M. В данном примере пропущен этап ввода массива M и символа sym. Реализация алгоритма с использованием цикла for.

char[] M = new char[10]; // заданный массив
char sym;
int i;
bool f;

// ввод массива M
// ...

// вычисление
f = false;
for (i = 0; i < 10; i++)
    if (M[i] == sym)
        f = true;

5. Определение наличия (отсутствия) заданного числа в массиве чисел. Массив имеет n целых чисел

Задан массив A целых чисел. Определить, есть ли заданное число num в массиве A.
Реализация с использованием цикла while (ввод массива A и переменных n, num пропущен).

// определение наличия (отсутствия) заданного числа в массиве чисел
int[] A = new int[50]; // заданный массив A
int n; // текущая размерность массива n = 1..50
int num; // искомое число
int i; // дополнительная переменная
bool f; // результат: f=true - число есть в массиве, иначе f=false

// ввод A, n, num
// ...

// вычисление
f = false;
i=0;

while (i<n)
{
    if (A[i] == num)
        f = true;
    i++;
}

6. Поиск позиции последнего вхождения элемента k в массиве из n целых чисел

Способ 1 (медленный).

В данном алгоритме результирующая переменная pos определяет позицию последнего вхождения элемента k в массиве из n целых чисел. Если такого символа нет в массиве, то pos = -1. Реализация с помощью цикла do…while

// поиск позиции последнего вхождения элемента k в массиве из n целых чисел
int[] A = new int[50]; // заданный массив A
int n; // текущая размерность массива n = 1..50
int k; // искомое число
int i; // дополнительная переменная
int pos; // результат - номер позиции, если pos=-1, то числа k не найдено в массиве A

// ввод A, n, k
// ...

// вычисление, реализация с помощью цикла do...while

pos = -1;
i=0;

do
{
    if (A[i] == k)
        pos = i;
    i++;
}
while (i<n);

Способ 2 (быстрый).

Если перебирать (пересматривать) индексы массива от конца к началу, то первый элемент равен k будет позицией последнего вхождения. В этом случае реализация алгоритма (цикл do…while) будет следующей

// поиск позиции последнего вхождения элемента k в массиве из n целых чисел
int[] A = new int[50]; // заданный массив A
int n; // текущая размерность массива n = 1..50
int k; // искомое число
int i; // дополнительная переменная
int pos; // результат - номер позиции, если pos=-1, то число k не найдено в массиве A

// ввод A, n, k
// ...

// вычисление, реализация с помощью цикла do..while

pos = -1;
i=n-1;

do
{
    if (A[i] == k)
    {
        pos = i;
        i=-1; // выход из цикла
    }
    else
        i--;
}
while (i>=0);

7. Поиск позиции первого вхождения элемента k в массиве из n целых чисел

Как было показано в предыдущем пункте, эту задачу можно решать разными способами. В нижеследующем коде массив пересматривается от начала к концу. Как только встречается элемент k, происходит запоминание позиции элемента k и выход из цикла.
Реализация задачи с использованием цикла for.

// поиск позиции первого вхождения элемента k в массиве из n целых чисел
int[] A = new int[50]; // заданный массив A
int n; // текущая размерность массива n = 1..50
int k; // искомое число
int i; // дополнительная переменная
int pos; // результат - номер позиции, если pos=-1, то число k не найдено в массиве A

// ввід A, n, k
// ...

// вычисление, реализация с помощью цикла for
pos = -1;
for (i=0; i<n; i++)
    if (A[i]==k)
    {
        pos = i;
        break; // выход из цикла
    }

8. Подсчет количества элементов k в массиве из n целых чисел

В нижеследующем коде пропущен ввод массива A и значений n, k.

// подсчет количества элементов k в массиве A
int[] A = new int[50]; // заданный массив A
int n; // текущая размерность массива n = 1..50
int k; // искомое число
int i; // дополнительная переменная
int count; // результат - количество найденных элементов

// ввод A, n, k
// ...

// вычисление, реализация с помощью цикла while
count=0;
i=0;
while (i<n)
    if (A[i++]==k)
        count++;

9. Подсчет количества элементов в массиве из n вещественных чисел, которые меньше заданного значения k

Реализация с помощью цикла do…while

// подсчет количества элементов, которые меньше заданного k
int[] A = new int[50]; // заданный массив A
int n; // текущая размерность массива n = 1..50
int k; // сравниваемое значение
int i; // дополнительная переменная
int count; // результат

// ввод A, n, k
// ...

// вычисление, реализация с помощью цикла while
count=0;
i=0;

do
{
    if (A[i]<k)
        count++;
    i++;
}
while (i<n);

10. Подсчет количества элементов в массиве из n вещественных чисел, значение которых находится в пределах диапазона [a .. b].

// подсчет количества элементов, которые лежат в заданном диапазоне
double[] M = new double[50]; // заданный массив M
int n; // текущая размерность массива n = 1..50
double a, b; // сравниваемые значения
int i; // дополнительная переменная
int count; // результат

// ввод A, n, a, b
// ...

// вычисление, реализация с помощью цикла for
count=0;
for (i=0; i<n; i++)
    if ((M[i]>=a)&&(M[i]<=b))
        count++;

11. Подсчет количества парных элементов в массиве из n целых чисел

// подсчет количества парных элементов в массиве целых чисел
int[] A = new int[50]; // заданный массив A
int n; // текущая размерность массива n = 1..10
int i; // дополнительная переменная
int count; // результат - количество парных элементов

// ввод A, n
// ...

// вычисление, реализация с помощью цикла for
count=0;
for (i=0; i<n; i++)
    if ((A[i]%2)==0)
        count++;

Связанные темы

• Одномерные массивы. Циклы for, while, do..while
• C#. Одномерные массивы. Примеры решения задач на одномерные массивы. Массивы структур. Массивы классов