Xyron10's blog

By Xyron10, history, 2 months ago, In English

For an array of n integers, the following operation can be performed on it any number of times: - Consider m to be the current size of the array arr. Then, k(1 <= k <= m) elements from the array with positions x1 , x1 , ...... xk can be removed from the array if 2^arr[x1] + 2^arr[x2] + ...... + 2^arr[xk] = 2^p for some non-negative integer p.

Given an array arr of n integers, find the minimum number of operations required to remove all elements from the array.

Example-

Consider n=5, arr = [1, 1, 3, 2, 3]. The following 2 operations can be performed to make the array empty: - In the first operation, remove arr, arr2 arr4, as their sum is 2^1+2^1+2^8 = 8 which is 2^3. Now, arr becomes [3,3]. - In the second operation, remove arr1, and arr2 as their sum is 2^3 +2^3 = 2^4. Now, arr becomes empty.

Hence, the answer is 2. It can be shown that the answer cannot be less than 2.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Xyron10, history, 3 months ago, In English

You are given a connected undirected graph having N nodes numbered from 1 to N and M edges between its nodes. It is guaranteed that the input graph is connected and consists of no self-loops and no multiple edges between two vertices. An edge is special if it is removed then the number of connected components in the graph increases. Determine the number of unordered_pair {u, v} such that each and every Simple path (path with no edges repeated) between the node u and node v consists of exactly 1 special edge.

Can anyone help me with this problem? Thank You.

Read more »

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