Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Freak_007's blog

Walmart Coding Round Problems
By Freak_007, history, 3 years ago, In English

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???

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
3 years ago, # |
← Rev. 4   Vote: I like it +8 Vote: I do not like it

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)

→ Reply
»
3 years ago, # |
  Vote: I like it +25 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    yes, that's correct

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did the same but it didn't passed all the test cases.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Problem in your code is that when you are calling b = (1 << j); then , overflow occurs. To avoid this use (1LL << j) this will convert int 1 to long long 1 and prevent overflow.

      → Reply
»
3 years ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

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
→ Reply