Picking Numbers

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 = { 122312 };
        List<Integerlist = Arrays.stream(arr).boxed().
                collect(Collectors.toList());
        System.out.println(pickingNumbers(list));
    }

    private static int pickingNumbers(List<Integerarr) {
        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<intarr)
{
    sort(arr.begin(), arr.end());
    int max1 = 1;
    int n = arr.size();
    for (int i = 0i < n - 1i++)
    {

        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(cntmax1);
    }
    return max1;
}
int main()
{
    int n = 6;

    vector<intarr = {122312};

    cout << pickingNumbers(arr);
    return 0;
}


No comments:

Post a Comment