Question

Magical Indices

Given an array of integers and a number

• x. An index is valid ifitem y at an index is increased by x and
• x+y would be greater than the sum of all other items in the array.

Write a JS program to determine the number of valid indices.

Input

• The first line of input contains an array
• The second line of input contains a number

Output

• The output should be a number indicating the number of valid positions

Explanation

For example, an array A = [10, 20, 30] and a value x = 25.

We have values 10, 20, 30 at indices 0,1,2 respectively.

• Here index 0 is invalid because
• 10 + 25 = 35 is less than 20 + 30 = 50
• Here index 1 is valid because
• 20 + 25 = 45 is greater than 10 + 30 = 40
• Here index 2 is valid because
• 30 + 25 = 55 is greater than 10 + 20 = 30

So there are 2 valid indices.

Sample Input 1

[1, 2, 3, 5, 7]

13

Sample Output 1

3

Sample Input 2

[34, 32, 37, 38, 40]

10

Sample Output 2

Answer 1

<script>
 
// Javascript program to find number of magical
// indices in the given array.

 
// Function to count number of magical indices.
function solve(A, n)
{
    var i, cnt = 0, j;
 
    // Array to store parent node of traversal.
    var parent = new Array(n + 1);
 
    // Array to determine whether current node
    // is already counted in the cycle.
    var vis = new Array(n + 1);
 
    // Initialize the arrays.
    parent.fill(-1);
    vis.fill(0);
 
    for(i = 0; i < n; i++)
    {
        j = i;
 
        // Check if current node is already
        // traversed or not. If node is not
        // traversed yet then parent value
        // will be -1.
        if (parent[j] == -1)
        {
             
            // Traverse the graph until an
            // already visited node is not
            // found.
            while (parent[j] == -1)
            {
                parent[j] = i;
                j = (j + A[j] + 1) % n;
            }
 
            // Check parent value to ensure
            // a cycle is present.
            if (parent[j] == i)
            {
                 
                // Count number of nodes in
                // the cycle.
                while (!vis[j])
                {
                    vis[j] = 1;
                    cnt++;
                    j = (j + A[j] + 1) % n;
                }
            }
        }
    }
    return cnt;
}
 
// Driver code
var A = [ 0, 0, 0, 2 ];
var n = A.length;
 
document.write(solve(A, n));  
 

 
</script>