Рубрики

Самый длинный префикс, который содержит одинаковое количество X и Y в массиве

Даны два натуральных числа X и Y и массив arr [] натуральных чисел. Нам нужно найти самый длинный индекс префикса, который содержит равное количество X и Y. Выведите максимальный индекс наибольшего префикса, если он существует, иначе выведите -1.

Примеры:

Input : array[] = [7, 42, 5, 6, 42, 8, 7, 5, 3, 6, 7]
        X = 7 Y = 42
Output : 9
The longest prefix with same number of occurrences 
of 7 and 42 is:
7, 42, 5, 6, 42, 8, 7, 5, 3, 6 42

Мы начинаем с индекса 0 и запускаем цикл до конца массива. Мы продолжаем увеличивать счетчики как для чисел X, так и для Y. После итерации по всему массиву последний результат, когда значения X и y равны, является нашим результатом.

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

C ++

// C ++ программа для поиска самого длинного префикса с
// равные числа X и Y.
#include<bits/stdc++.h>

using namespace std;

  
// Функция для поиска максимального индекса наибольшего
// префикс с тем же номером, если X и Y

int findIndex(int arr[], int X, int Y, int n)

{

    // счетчики для X и Y

    int nx = 0,ny = 0;

  

    int result = -1;

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

    {

        // Если значение равно счетчику приращений X

        if (arr[i]==X)

            nx++;

  

        // Если значение равно счетчику приращений Y

        if (arr[i]==Y)

            ny++;

  

        // Если счетчики равны (но не равны нулю) сохранить

        // результат как я

        if ((nx != 0) && (nx == ny))

            result = i;

    }

    return result;

}

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

int main()

{

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

    int X = 7, Y = 42;

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

    cout << "Ending index of prefix is "

         << findIndex(arr, X, Y, n);

  

    return 0;

}
// Улучшено Цюй Дунфаном.

Джава

// Java программа для поиска самой длинной
// префикс с равными номерами
// из X и Y.

import java.io.*;

  

public class GFG

{

      
// Функция для поиска максимального индекса
// самого большого префикса с таким же
// число, если X и Y

static int findIndex(int []arr, int X,

                     int Y, int n)

{

      

    // счетчики для X и Y

    int nx = 0, ny = 0;

  

    int result = -1;

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

    {

        // Если значение равно X

        // увеличить счетчик X

        if (arr[i] == X)

            nx++;

  

        // Если значение равно Y

        // увеличить счетчик Y

        if (arr[i] == Y)

            ny++;

  

        // Если счетчики равны (но не

        // ноль) сохранить результат как я

        if ((nx != 0) && (nx == ny))

            result = i;

    }

      

    return result;

}

  

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

    static public void main (String[] args)

    {

    int []arr = {7, 42, 5, 6, 42, 8

                 7, 5, 3, 6, 7};

    int X = 7, Y = 42;

    int n = arr.length;

    System.out.println("Ending index of prefix is "

        + findIndex(arr, X, Y, n));

    }

}

  
// Этот код предоставлен vt_m.
// Улучшено Цюй Дунфаном.

python3

# Python 3 программа для поиска самого длинного префикса
# с равными числами X и Y.

  
# Функция для поиска максимального индекса
# самый большой префикс с тем же номером
# если X и Y

def findIndex(arr, X, Y, n):

      

    # счетчики для X и Y

    nx = 0

    ny = 0

  

    result = -1

    for i in range(n):

          

        # Если значение равно приращению X

        # счетчик X

        if arr[i] == X:

            nx += 1

  

        # Если значение равно приращению Y

        # счетчик Y

        if arr[i] == Y:

            ny += 1

  

        # Если счетчики равны (но не равны нулю)

        # сохранить результат как я

        if nx and (nx == ny):

            result = i

  

    return result

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

if __name__ == '__main__':

    arr = [7, 42, 5, 6, 42, 8, 7, 5, 3, 6, 7]

    X = 7

    Y = 42

    n = len(arr)

    print("Ending index of prefix is",

              findIndex(arr, X, Y, n))

  
# Этот код предоставлен
# Sanjit_Prasad
# Улучшено Цюй Дунфаном.

C #

// C # программа для поиска самой длинной
// префикс с равными номерами
// из X и Y.

using System;

  

public class GFG

{

      
// Функция для поиска максимального индекса
// самого большого префикса с таким же
// число, если X и Y

static int findIndex(int []arr, int X,

                     int Y, int n)

{

      

    // счетчики для X и Y

    int nx = 0, ny = 0;

  

    int result = -1;

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

    {

        // Если значение равно X

        // увеличить счетчик X

        if (arr[i] == X)

            nx++;

  

        // Если значение равно Y

        // увеличить счетчик Y

        if (arr[i] == Y)

            ny++;

  

        // Если счетчики равны (но не

        // ноль) сохранить результат как я

        if ((nx != 0) && (nx == ny))

            result = i;

    }

      

    return result;

}

  

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

    static public void Main (String []args)

    {

    int []arr = {7, 42, 5, 6, 42, 8, 

                 7, 5, 3, 6, 7};

    int X = 7, Y = 42;

    int n = arr.Length;

    Console.WriteLine("Ending index of prefix is "

        + findIndex(arr, X, Y, n));

    }

}

  
// Этот код предоставлен vt_m.
// Улучшено Цюй Дунфаном.

PHP

<?php
// PHP программа для поиска самого длинного префикса с
// равные числа X и Y.

  
// Функция для поиска максимального индекса наибольшего
// префикс с тем же номером, если X и Y

function findIndex($arr, $X, $Y, $n)

{

    // счетчики для X и Y

    $nx = 0; $ny = 0;

  

    $result = -1;

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

    {

        // Если значение равно приращению X

        // счетчик X

        if ($arr[$i] == $X)

            $nx++;

  

        // Если значение равно приращению Y

        // счетчик Y

        if ($arr[$i] == $Y)

            $ny++;

  

        // Если счетчики равны (но не равны нулю)

        // сохранить результат как я

        if (($nx != 0) && ($nx == $ny))

            $result = $i;

    }

    return $result;

}

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

$arr = array(7, 42, 5, 6, 42, 8, 

                  7, 5, 3, 6, 7);

$X = 7; $Y = 42;

$n = sizeof($arr);

echo "Ending index of prefix is "

       findIndex($arr, $X, $Y, $n);

  
// Этот код добавлен
// Аканкша Рай
// Улучшено Цюй Дунфаном.
?>


Выход:

Ending index of prefix is 9

Временная сложность: O (n)

Ссылка :
https://www.careercup.com/question?id=6194336212451328

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

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

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

Самый длинный префикс, который содержит одинаковое количество X и Y в массиве

0.00 (0%) 0 votes