Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
1,097 views
in Online Assessments by Expert (46,090 points) | 1,097 views

2 Answers

0 like 0 dislike
Best answer

A beautiful subarray is defined as an array of length having a specific number of odd elements. Given an array of integers and a number of odd elements that constitutes beauty, create as many distinct beautiful subarrays as possible. Distinct means the arrys dont share identical starting and ending indices, though they may share one of the two.
For example, given the array [1,2,3,4,5] and a beautiful number 2, the following beautiful subarrays can be formed.
[1,2,3]
[1,2,3,4]
[2,3,4,5]
[3,4,5]
output: 4

 

More Example
[2,5,4,9] , 2

 

subarrays
[5,4,9]
[2,5,4,9]
output:2

by Expert (46,090 points)
0 like 0 dislike

C++ solution. Brute force (O(n^2)) and Sliding Window Implementation (O(n))

 

#include<vector>
#include<iostream>

using namespace std;

int findSubarray(vector<int> nums, int n){
	int count = 0;

	for (int i = 0; i<nums.size(); i++){
		int odd = 0;
		for (int j = i; j<nums.size(); j++){
			if (nums[j] % 2 != 0)
				odd++;
			if (odd > n){
				break;
			}
			if (nums[i] != nums[j] && odd == n){
				cout << nums[i] << "  " << nums[j] << endl;
				count++;
			}

		}
	}
	return count;

}

int findSubarraySlidingWindow(vector<int> nums, int n){
	int windowStart = 0, odd = 0;
	int count = 0;

	for (int windowEnd = 0; windowEnd < nums.size(); windowEnd++){
		if (nums[windowEnd] % 2 != 0){
			odd++;
		}
		if (odd == n && nums[windowStart] != nums[windowEnd]){
			cout << nums[windowStart] << " " << nums[windowEnd] << endl;
			count++;
		}
		while(odd > n){
			// shrink the window
			if(nums[windowStart++] % 2 != 0){
				odd--;
			} 
			if (odd == n && nums[windowStart] != nums[windowEnd]){
				cout << nums[windowStart] << " " << nums[windowEnd] << endl;
				count++;
			}
		}
	}

	int windowEnd = nums.size() -1;
	// There could be more even numbers at front so we could still shrink it even though we are at the end of the array. 
	while(odd >= n){
		// shrink the window
		if(nums[windowStart++] % 2 != 0){
			odd--;
		} 
		if (odd == n && nums[windowStart] != nums[windowEnd]){
			cout << nums[windowStart] << " " << nums[windowEnd] << endl;
			count++;
		}
	}

	return count;
}



int main(void){	
	int ewa = findSubarray({2,5,4,9}, 2);
	cout << "result " << ewa << endl;
	cout << "find subarray sliding window" << endl;
	int result = findSubarraySlidingWindow({2,5,4,9}, 2);
	cout << "result " << result << endl;
	return 0;
}
by Expert (46,090 points)