Tricky Edge Case in Data Structures and Algorithms

Algorithms and Data Structures In Action Version 13 HD wallpaper

Question

Problem statement

Input and Expected Output

Constrains

Sample Test Cases

Input :-

Output :-

YES
3 6 3 6
NO
YES
2 4 1 5 3
YES
1 4 4

Understanding the Question

This figure helps us to visualize an ugly array. These arrangement of elements where an element is EXACTLY equal to sum of ALL THE ELEMENTS before it, makes an array ugly. ( In the above figure, it's element X's and Y's position that makes the array ugly and creates trouble. )

I use this idea of visualizing elements as LINES or BARS very often

The height of al element is indicative of the VALUE of the array element.
The color helps us to identify which element is creating trouble
Sum of all elements from 1 to 5 is same as the value of 6th element => Brown bar
Sum of all elements from 1 to 8 is same as the value of 9th element => Brown bar

Now we need to make this array BEAUTIFUL :-

there should not be any arrangement where sum of elements from index 1 to k is same as the (k+1)th element

Basic Intuition

If we swap k and (k+1)th that should probably be enough. Since now sum of elements from 1 to k will not be the (k+1)th element.

Let's try to prove it visually :-

While making this diagram, I came up with a cute little mathematical proof that is really easy and intuitive :-

We know that by definition of ugly array :-

$$\sum_{1}^{k}a_i = a_{k+1}$$

Now if we swap a_k and a_{k+1} :

$$a_1 + a_2 + \dots + a_k > a_{k+1}$$

$$\Rightarrow \sum_{1}^{k}a > a_{k+1}$$

Hence the logic works, we can remove the the "problem-arrangement".

Coding out the Basic Intuition

Basic body should look like something like this :-

int a[50]; // an input array 
int s[50]; // a cumulative sum array ( prefix-sum array )

void solve(){
    int t,n; s[0]=0; cin >> t;
    while(t--){
        // solve for each test_case
    }
}

We'll keep track of all the problem indices which makes the array ugly :-

while(t--){
        cin >> n; int found = 0, edge_case = 0;
        vector<int> idx; // all problem indices 

        for(int i=1 ; i<=n ; i++){ 
            cin>>a[i];
            s[i] = s[i-1]+a[i]; // populating the prefix array
            if( a[i]==s[i-1] ) idx.push_back(i); // checking for ugly condition
        }

Later we'll swap the sum_element to be "inside" the sum 1 to k

 for(int i : idx) swap(a[i],a[i-1]); // swap the sum_element to it's left side

 cout<<"YES\n";for(int i=1;i<=n;i++)cout<<a[i]<<" ";
 cout<<"\n";

The Edge case that seemed obvious

Now another question :-

When can an ugly array IMPOSSIBLE to make beautiful ?

The example they provided in the test case gives us an idea :-

If there are only 2 elements and both are equal to each other, there is no way to make this array beautiful.

Sum of elements from 1 to 1 is same as the 2nd element. Even if you swap, we can't make this array beautiful.

Code to take care of that Edge case

if(n==2 && a[0]==a[1])cout<<"NO\n";

Generalizing the Edge Case

But a little for thought makes us realize that, the idea :-

If there are only 2 elements and both are equal to each other, there is no way to make this array beautiful.

Isn't completely correct.

The array length has nothing to do with the fact that first 2 elements are same.

In fact the below arrangement also has the same problem.

And this arrangement too :-

The fundamental problem is :-

if a_1 == a_2 &&

you can't find any element that to swap a_2 with

So we can try to generalize all these kinds edge case to a singe type.

Generalizing the ONLY important Edge Case :=

ONLY IF a_1 == a_2, there is a possibility for this edge case, being the case.
Try to find an element in the array that is DIFFERENT from a_1 ( same some X )
SWAP a_2 and X

Code to take care of any the generalized Edge Case

I am particularly proud of this code since this is code exactly does what I wanted it to AND ONLY what I want it to, it's really clean and easy to understand.

Complete Code

So the complete solution would look like :-

#include <iostream>
#include <vector>
using namespace std;


int a[50]; int s[50];

void solve(){
    int t,n; s[0]=0; cin >> t;
    while(t--){
        cin >> n; int found = 0, edge_case = 0;
        vector<int> idx;

        for(int i=1 ; i<=n ; i++){ 
            cin>>a[i];
            s[i] = s[i-1]+a[i]; 
            if( i>2 && a[i]==s[i-1] ) idx.push_back(i);
        }

        if(a[1]==a[2]){
            edge_case = 1;
            for(int i=3;i<=n;i++)if(a[i] != a[1]){
                found = 1; 
                swap(a[1],a[i]); 
            }
        }
        if(edge_case && !found){ cout<<"NO\n";continue; }


        for(int i : idx) swap(a[i],a[i-1]);

        cout<<"YES\n";for(int i=1;i<=n;i++)cout<<a[i]<<" ";
        cout<<"\n";
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    solve();
}

Thank you,

__CPP_Try_Hard__ ;