Problem Brief

Count Ways to Reach a Sum

FULLTIMEOA

See Uber online assessment and hiring insights

🐰 🐹 🐶 🐻‍❄️ Click the source image button below to view the original problem statement👇 Pls don't hesitate to reach out to us if the source image is broken.. We are all on the discord serva

Once upon a time in the land of Algorithmlandia, there were two mystical arrays of integers named a and b. These arrays lived peacefully, each filled with unique numbers. The residents of Algorithmlandia often found themselves puzzled by the secrets these arrays held, so they turned to a wise sage who could process their queries and uncover the hidden truths.

One day, the people brought forth an array of queries to the sage. Each query held a special request. Some queries came in the form of a spell:

"[0, i, x]" - this spell was cast to enhance the magical power of the b array. The spell added the number x to the current value at the i-th position of b. This transformation often led to interesting changes in the array's magic.

Other queries arrived with a different incantation:

"[1, x]" - this spell sought to uncover pairs of numbers from a and b that held a special bond. The query requested the sage to count all pairs of indices (i, j) such that the sum of a[i] and b[j] equaled the mystical number x.

With each query processed in the given order, the sage carefully recorded the results of the second type of spell. These results were then compiled into an array, reflecting the wisdom and insights gained from the magical arrays a and b.

And so, the people of Algorithmlandia marveled at the sage's ability to decipher the secrets of the arrays, their lives enriched by the knowledge revealed through the queries. The story of the arrays and the sage's wisdom was passed down through generations, a testament to the power of understanding and the magic of numbers.

1Example 1

Input

a = [1, 2, 3], b = [1, 4], queries = [[1, 5], [0, 0, 2], [1, 5]]

Output

[1, 2]

Explanation

Once upon a time in Algorithmlandia, there lived two enchanted arrays, a and b. The array a had the values [1, 2, 3], while the array b held the values [1, 4]. The wise sage, known for unraveling the mysteries of numbers, was approached with a series of magical queries to solve. The first query was of the second type, [1, 5]. The people were eager to know how many ways they could form the number 5 by adding one element from array a to one element from array b. The sage pondered and quickly realized that there was only one such pair: a[0] + b[1] = 1 + 4, which equaled 5. The sage declared the result to be 1. Next, a spell of transformation was cast upon the b array with the query [0, 0, 2]. This spell added 2 to the first element of b, changing it to [3, 4]. The landscape of the arrays had shifted. The people, intrigued by the changes, presented the sage with another query of the second type, [1, 5]. This time, the sage found not one, but two pairs that summed to 5. The pairs were a[1] + b[0] = 2 + 3 and a[2] + b[0] = 3 + 2. The sage announced that there were now 2 ways to form the sum of 5. And so, the sage's wisdom continued to illuminate the path for the people of Algorithmlandia, revealing the hidden connections between the enchanted arrays. Each query added a new layer of understanding, and the people marveled at the magic woven through the numbers.

Constraints

Limits and guarantees your solution can rely on.

🐿️