5 weeks ago

John 910

Hyderabad

Question 1

Merge Elements

Given an array X containing N integers. You can perform the following operation on the array elements: for any two elements in the array (a, b) you can merge element b into element a if 2a >= b. The numbers add together when merged.

You have to perform this operation until only one element remains in the array. Return the number of positions possible for the final number.

Example of merging operation:

X = [3,4]

• We can merge 4 into 3 as 2 • 3 ≥ 4 resulting in array X = [7, ]

• We can merge 3 into 4 as 2 • 4 ≥ 3 resulting in array X = [,7]

Input Format

• First line contains single integer: number of test cases (t)

• Each test case contains two lines: 

            • First line contains N

            • Second line contains array X

Constraints

1 ≤ t ≤ 10

1 ≤ N ≤ 10⁵

1 ≤ X_i ≤10⁹

Output Format

For each test case output a line with the number of possible positions for the final number. 

Sample Test Case #0

Input:

1

4

2 3 1 4

Output:

4

Explanation:

The four final states can be reached as follows: 

[2,3,1,4] → [5, ,1,4] → [6, , ,4] → [10, , , ] 

[2,3,1,4] → [ ,5,1,4] → [ ,6, ,4] → [ ,10, , ] 

[2,3,1,4] → [ ,3,3,4] → [ ,3,7, ] → [ , ,10, ] 

[2,3,1,4] → [2,3, ,5] → [2, , ,8] → [ , , ,10]

Sample Test Case #1

Input:

1

2

1 3

Output:

1

Explanation:

As 2.1 ≱  3, The only possible final state of X is [ ,4]

12 months ago

Apna_time _aayega • 60

Why the ans is being updated Once we get the ans then for all elements below that "i" will fail to have the final element at that i
Means why we can not use break statement after finding that answer
for(int i = n-2; i >= 0; i--){
        int a = prefixsum[i];
        if(arr[i+1]>(2*a)){
          ans = n-i-1;
          break;
        }
    }
    return ans;

10 months ago

Manas 310

Bānswāra

Question 1

• Observation 1 - There can be n final positions at max, all that matters is if a position is possible or not, if a position corresponding to an element is possible, then that element will never move from its place.
• Observation 2 - If our final position corresponds to an element aj, the all ai <= aj will for sure move to this position trivially. if a < = b implies a < = 2*b
• Observation 3 - If the position corresponding to an element is possible, then all the positions corresponding to values greater than that element will also be possible. Now all we need to find is the smallest element corresponding to which the mentioned operation in the question is possible.

Solution

We will sort the array arr and take prefix sum. It is obvious that for the last element the answer is always possible (from observation 2). We will have a pointer pt from the second last element and check if 2*prefix[pt] >= arr[pt+1] then move the pointer one step lower to the next smaller element, i.e pt--. If we can reach the element at pt, then we can reach the next element as well, which is understood from the condition we check before moving the pointer. We check 2*prefix[pt] because we know from observation 2 that all smaller elements can reach here trivially and then value will sum up till that position.

In the end we will get the number of elements for which we can reach a single element, hence all position corresponding to this element will be the positions which can be reached, and the final answer would hence be the number of elements from which we can use the mentioned operation to reach a single element.

pseudo code:

for(int i = n-2; i>= 0; i--)
{
    if(2*prefix[i] >= arr[i+1])
        continue;
    else
    {
        ans = n - i - 1;
    }
}

18 days ago

Gyomei Himejima • 0

Indore

1
6
1 2 10 20 100 200

For this test case there is no way elements can merge into 1 , 2, 10 and 20 as even if we sum all elements appearing before 20 it sums to 33 and 33*2 < 100. But the expected answer is 4. So using break is logically incorrect but all the  test cases are getting passed after using break. Please correct me if I am wrong.

#include <bits/stdc++.h>
  using namespace std;
#define int long long

  signed main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

    
    int t;
    cin >> t;
    
    while(t--){
      
      int n;
      cin >> n;
      int arr[n];
      for(int i =0 ; i< n ; i++){
        cin >> arr[i];
      }
      
      sort(arr,arr+n);
      
      int sum=0;
      
      int j=0;
      
      for(int i = 0 ; i < n-1 ; i++){
        sum += arr[i];
        if(2*sum < arr[i+1]){
          j = i+1;
          break;
        }
      }
      
      cout << n-j << endl;
      
      
    }

    return 0;

  }