Header Ads Widget

Alternating subarray prefix | codechef solution

Alternating subarray prefix

There's an array A consisting of N non-zero integers A1..N. A subarray of A is called alternating if any two adjacent elements in it have different signs (i.e. one of them should be negative and the other should be positive).

For each x from 1 to N, compute the length of the longest alternating subarray that starts at x - that is, a subarray Ax..y for the maximum possible y ≥ x. The length of such a subarray is y-x+1.

Input

  • The first line of the input contains an integer T - the number of test cases.
  • The first line of each test case contains N.
  • The following line contains N space-separated integers A1..N.

Output

For each test case, output one line with N space-separated integers - the lengths of the longest alternating subarray starting at x, for each x from 1 to N.

Constraints

  • 1 ≤ T ≤ 10
  • 1 ≤ N ≤ 105
  • -109 ≤ Ai ≤ 109

Sample 1:

Input
Output
3
4
1 2 3 4
4
1 -5 1 -5
6
-5 -1 -1 2 -2 -3
1 1 1 1
4 3 2 1
1 1 3 2 1 1

Explanation:

Example case 1. No two elements have different signs, so any alternating subarray may only consist of a single number.

Example case 2. Every subarray is alternating.

Example case 3. The only alternating subarray of length 3 is A3..5

Solution:-

  
#include <stdio.h>

int main() {
int t, n, i;
int a[100009];
int len[100009];
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
len[n - 1] = 1;
for (i = n - 2; i >= 0; i--) {
if (a[i] * (long long)a[i + 1] < 0) { // Casting to long long for multiplication to avoid overflow
len[i] = len[i + 1] + 1;
} else {
len[i] = 1;
}
}
printf("%d", len[0]);
for (i = 1; i < n; i++) {
printf(" %d", len[i]);
}
printf("\n");
}
return 0;
}
#include <iostream>
#include <vector>

using namespace std;

int main() {
int t, n;
cin >> t;
while (t--) {
cin >> n;
vector<int> a(n), len(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
len[n - 1] = 1;
for (int i = n - 2; i >= 0; i--) {
if (a[i] * (long long)a[i + 1] < 0) {
len[i] = len[i + 1] + 1;
} else {
len[i] = 1;
}
}
cout << len[0];
for (int i = 1; i < n; i++) {
cout << " " << len[i];
}
cout << endl;
}
return 0;
}
}for _ in range(int(input())):
n=int(input())
ints=list(map(int,input().split()))
ans=[0]*n
ans[-1]=1
j=0
# for j in range(size-1):
while(j<n-1):
# m_count=1
count=1
for i in range(j,n-1):
if(ints[i]<0):
if(ints[i+1]>0):
count+=1
else:
# If both ints are having same sign then, just compare with m_count and
# update it
# if(count>=m_count):
# m_count=count
break
else:
if(ints[i+1]<0):
count+=1
else:
# Same sign so, now check and update
# if(count>=m_count):
# m_count=count
break
itr=count
while(itr>0):
ans[j]=itr
j+=1
itr-=1
print(*ans)
Text Copied!




easycodingzone

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-

Post a Comment

0 Comments