Question

Given an array of n integers, find the longest leading fragment of array which contains equal no. Of x and y. Expected time complexity is o(n)

Answer 1

Answer:

Program in C language written.

Step-by-step explanation:

// A program in C language to find the longest leading fragment  

// of array containing equal number of x and y.

#include <stdio.h>

main()

{

  int A[100], n, x, y, cnt1, cnt2, i=0, index=0 ;

    printf("input n: ");

    scanf("%d",&n);

    printf("input Array : ");

    for (i=0;i<n;i++) scanf("%d",&A[i]);

    cnt1 =0; cnt2=0;

    for (i=0, index=0; i<n; i++) {

        if (A[i] == x) cnt1++ ;

       else if (A[i] == y) cnt2++;

       if (cnt1 == cnt2) index = i;

  }  

  // A[1..index] is the leading fragment of array

 // with equal number of x and y.

}

Answer 2

ANSWER:------

Given two positive integers X and Y, and an array arr[] of positive integers.

We need to find the longest prefix index which contains an equal number of X and Y.

Print the maximum index of largest prefix if exist otherwise print

-1.Examples: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

hope it helps:)

T!—!ANKS!!!