CODEWITHSUNDEEP
javaalgorithm
Learner
Learner

Reputation: 21393

Given an array with difference between adjacent numbers find the original array possibilities

Given an array holding the difference between a pair of consecutive integers and lower and upper limits, find the number of possible arrays that can meet these criteria.

example:

array = [-2, -1, -2, 5]
lowe limit = 3;
upper limit = 10

Ans:
3

explanation:

possible arrays are :
[3,5,6,8,3] => here each element is within limits and difference between adjacent elements is [-2,-1,-2,5]
[4,6,7,9,4] => same as above
[5,7,8,10,5]  => same as above

Here is my program but this is not the correct approach that I am using as this program is failing for several test cases in hackerrank some days back:

public static int process(List<Integer> arr, int lower, int higher) {
    int max = Integer.MIN_VALUE;
    int n = lower;
    for (int i = 0; i < arr.size(); i++) {
        int k = arr.get(i);
        int k1 = n - k;
        if (k1 > higher || k1 < lower) {
            return 0;
        }
        n = k1;
        max = Math.max(max, n);
    }

    max = higher - max + 1;

    return max;
}

What is the correct approach for this task?

Upvotes: 1

Views: 9687

Answers (4)

danisherror
danisherror

Reputation: 1

Same question asked in Oracle Sde interview on campus. passed all test cases.

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    vector<int>ans;
    int io=0;
    ans.push_back(0);
    for(int i=0;i<n;i++)
    {
        if(a[i]<=0)
        {
            io=io+abs(a[i]);
        }
        else
        {
            io=io-a[i];
        }
        ans.push_back(io);
    }
    sort(ans.begin(),ans.end());
    int d=0;
    int a1,b1;
    cin>>a1>>b1;
    for(int i=a1;i<=b1;i++)
    {
        int io;
        io=i+ans[0];
        if(io>=a1 && io<=b1)
        {
            io=i+ans[ans.size()-1];
            if(io>=a1 && io<=b1)
            {
                d++;
            }
        }
    }
    cout<<d;
    
    
}

Upvotes: 0

unicdev
unicdev

Reputation: 322

This is the Python solution:

def countAnalogousArrays(consecutiveDifference , lowerBound , upperBound):

    maxdiff = float('-inf')
    mindiff = float('inf')
    runningsum = 0
    if len(consecutiveDifference) == 0:
        return 0

    if upperBound < lowerBound :
        return 0

    for diff in consecutiveDifference:
        runningsum+=diff
        if runningsum > maxdiff:
            maxdiff = runningsum

        if runningsum < mindiff:
            mindiff = runningsum

    maxvalidupperbound = upperBound + mindiff if upperBound+mindiff < upperBound else upperBound
    minvalidlowerbound = lowerBound + maxdiff if lowerBound + maxdiff > lowerBound else lowerBound

    if maxvalidupperbound >= minvalidlowerbound:
        return maxvalidupperbound - minvalidlowerbound + 1
    else:
        return 0

Upvotes: 1

gishac
gishac

Reputation: 31

public static void main(String[] args) {
    // TODO Auto-generated method stub
    
    List<Integer> baseArray = new ArrayList<>();
    baseArray.add(-2);
    baseArray.add(-1);
    baseArray.add(-2);
    baseArray.add(5);
    int lower = 3;
    int upper = 10;
    int arrayMatches = 0;
    
    for(int i=lower; i<=upper; i++) {
        boolean match = false;
        int[] array = new int[baseArray.size() + 1];
        int matchCount = 0;
        for(int j = 0; j<=array.length-1; j++) {
            
            if(j == 0) {
                array[j] = i;
                continue;
            }
                
            int matchValue = baseArray.get(j -1);
            
            for(int b=lower; b<=upper;b++) {
                if(array[j-1] - b == matchValue) {
                    matchCount++;
                    array[j]=b;
                }
            }
                
        }
        if(matchCount == baseArray.size()) {
            arrayMatches++;
        }
    }
    System.out.println(arrayMatches);

}

Upvotes: 0

sprinter
sprinter

Reputation: 27946

Looks to me like you've got the logic correct. Could you give some failing test cases?

I think you could simplify things quite a bit as the variable names you've chosen and the structure of your code makes things a bit harder to review:

int min = 0;
int max = 0;
int current = 0;

for (int val: arr) {
    current += val;
    min = Math.min(min, current);
    max = Math.max(max, current);
}

return Math.max(0, (higher - lower) - (max - min) + 1);

A difference in my code is that I just calculate difference from the first number as I iterate through the array and don't use the actual range until the answer is calculated. That makes the algorithm a bit simpler to follow (IMO).

Upvotes: 2

Related Questions