Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

Блог пользователя Freak_007

Walmart Coding Round Problems
Автор Freak_007, история, 3 года назад, По-английски

Got asked these in Walmart coding round:

A. Given a number n. To find two numbers a and b such that 

     a xor b = n
     b >= a and (b - a) should be minimum
     for all the a and b which satisfy the above conditions a and b should be minimum
     1 <= n <= 1e12
  • My Soln: for(j = 0; j <= 62; j++) if((n >> j) & 1) b = (1 << j); a = n - b;
  • Result: Partial testcase passed
  • Weightage: 20 pts.

B. Given an array A of size n and a number K. Have to find the number of subarrays [l, r] such that:

    (r - l + 1) = K * (sum of all elements of subarray [l, r])
    1 <= n <= 1e5
    |K| >= 1
    -1e6 <= A[i] <= 1e6
  • My Soln: Wrote O(n * n) soln. Spoiler Alert got TLE.
  • Weightage: 30 pts.

How can I have solved these???

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
3 года назад, # |
← Rev. 4   Проголосовать: нравится +8 Проголосовать: не нравится

For the 2nd problem

Equation 1) Sum of a subarray[l, r] -> prefixSum[r] — prefixSum[l-1]

Equation 2) r — l + 1 = (k * prefix_sum[r]) — (k * prefix_sum[l-1])

Equation 3) r — (k * prefix_sum[r]) = l — 1 — (k * prefix_sum[l-1])

So, first, calculate, prefix_sums and intiliaze prefix_sum[-1] = 0

Now, maintain an occurence table for the right side of the equation 3 above. For this purpose, you can use an unordered_map or ordered_map.

After that, iterate from left-to-right and for each index increment the occurence by 1, for the following expression -> (i — 1 — (k * prefix_sum[i-1])) (Right side of the 3rd equation)

Lastly, for each index i, update the answer by frequency of the following expression -> (i — (k * prefix_sum[i]))(Left side of the 3rd equastion)

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

For A, you can give the largest set bit to b, while other set bits to a. Unset bits should be set to 0 for both. I think that should work. Correct me if I am wrong

→ Ответить
»
3 года назад, # |
← Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

WELP , I misread it,I thought K*(r-l+1)=sum of elements in the range, sorry for trouble.

→ Ответить
»
3 года назад, # |
← Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

Problem B Solution

prefix_l-1 (-1 is with the name of variable) to hold sum from 1 to l-1 
r-l+1 = k*(prefix_r - prefix_l-1);
r-l+1 = k*prefix_r - k*prefix_l-1;
k*prefix_r - r = k*prefix_l-1 - l +1;
k*prefix_r - r = k*prefix_l-1 - (l-1);
so let current index be r , calculate sum as sum = k*prefix_from_1_to_r - r;
look up in map , how many previous indexes (l-1 or say i) have prefix_sum_from_1_to_i = sum , add that to your answer ;
update the map with your sum
→ Ответить