In this HackerEarth Minimum indexes problem solution You are given an array A of Q integers and Q queries. In each query, you are given an integer i (1 <= i <= N).

Your task is to find the minimum index greater than i (1 <= i <= N) such that:
  1. Sum of digits of Ai is greater than the sum of digits of Aj
  2. Ai < Aj
If there is no answer, then print -1.


HackerEarth Minimum indexes problem solution


HackerEarth Minimum indexes problem solution.

#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define endl "\n"
#define ll long long
#define sz(s) (int)(s.size())
#define INF 0x3f3f3f3f3f3f3f3fLL
#define all(v) v.begin(),v.end()
#define watch(x) cout<<(#x)<<" = "<<x<<endl
const int dr[] { -1, -1, 0, 1, 1, 1, 0, -1 };
const int dc[] { 0, 1, 1, 1, 0, -1, -1, -1 };
#if __cplusplus >= 201402L
template<typename T>
vector<T> create(size_t n) {
    return vector<T>(n);
}
template<typename T, typename ... Args>
auto create(size_t n, Args ... args) {
    return vector<decltype(create<T>(args...))>(n, create<T>(args...));
}
#endif
void run() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#else
#endif
}

struct segment_tree {
#define LEFT (idx<<1)
#define RIGHT (idx<<1|1)
#define MID ((start+end)>>1)
    int n;
    vector<int> tree;
    segment_tree(int n = 0) :
            n(n), tree(n << 2) {
    }
    void update(int idx, int start, int end, int pos, int val) {
        if (start == end) {
            tree[idx] = val;
            return;
        }
        if (pos <= MID)
            update(LEFT, start, MID, pos, val);
        else
            update(RIGHT, MID + 1, end, pos, val);
        tree[idx] = max(tree[LEFT], tree[RIGHT]);
    }
    int query(int idx, int start, int end, int l, int r, int val) {
        if (r < start || end < l || tree[idx] <= val)
            return n;
        if (start == end)
            return start;
        int rt = query(LEFT, start, MID, l, r, val);
        if (rt < n)
            return rt;
        return query(RIGHT, MID + 1, end, l, r, val);
    }
    void update(int pos, int val) {
        update(1, 0, n - 1, pos, val);
    }
    int query(int l, int r, int val) {
        return query(1, 0, n - 1, l, r, val);
    }
} seg[9 * 9 + 1];

int sumDigits(int a) {
    if (a == 0)
        return 0;
    return a % 10 + sumDigits(a / 10);
}
int main() {
    run();
    int n, q;
    cin >> n >> q;
    for (int i = 0; i <= 81; i++)
        seg[i] = segment_tree(n);
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        seg[sumDigits(v[i])].update(i, v[i]);
    }
    while (q--) {
        int i;
        cin >> i;
        i--;
        int sum = sumDigits(v[i]);
        int ans = n;
        for (int j = 0; j < sum; j++)
            ans = min(ans, seg[j].query(i + 1, n - 1, v[i]));
        if (ans == n)
            ans = -2;
        cout << ans + 1 << endl;
    }
}

Second solution

[n, q] = map(int, input().split())
a = list(map(int, input().split()))
while q > 0:
    q -= 1
    i = int(input()) - 1
    ans = -2
    for j in range(i + 1, n):
        if a[i] < a[j] and sum(map(int, str(a[i]))) > sum(map(int, str(a[j]))):
            ans = j
            break
    print(ans + 1)