Given an array of integers, find the longest subarray where the absolute difference between any two elements is less than or equal to 1.
Example:
Input: n=6, arr[]={1,2,2,3,1,2}
Output: 5
Approach
Java
import java.util.Arrays;import java.util.Collections;import java.util.List;import java.util.stream.Collectors;public class PickingNumbers {public static void main(String[] args) {int[] arr = { 1, 2, 2, 3, 1, 2 };List<Integer> list = Arrays.stream(arr).boxed().collect(Collectors.toList());System.out.println(pickingNumbers(list));}private static int pickingNumbers(List<Integer> arr) {Collections.sort(arr);int max1 = 1;int n = arr.size();for (int i = 0; i < n - 1; i++) {int x = arr.get(i);int cnt = 1;while (i<n-1&& Math.abs(arr.get(i + 1) - x) <= 1&& Math.abs(arr.get(i) - x) <= 1&& Math.abs(arr.get(i + 1) - arr.get(i)) <= 1) {cnt++;i++;}max1 = Math.max(cnt, max1);}return max1;}}
C++
#include <bits/stdc++.h>using namespace std;int pickingNumbers(vector<int> arr){sort(arr.begin(), arr.end());int max1 = 1;int n = arr.size();for (int i = 0; i < n - 1; i++){int x = arr[i];int cnt = 1;while (abs(arr[i + 1] - x) <= 1 &&abs(arr[i] - x) <= 1 &&abs(arr[i + 1] - arr[i]) <= 1){cnt++;i++;}max1 = max(cnt, max1);}return max1;}int main(){int n = 6;vector<int> arr = {1, 2, 2, 3, 1, 2};cout << pickingNumbers(arr);return 0;}
No comments:
Post a Comment