Index of the array which would be visited in Kth operation | By The Digital Insider

on

Given an array A[] of length N such that A[i] = i for all indices. Also, given two integers K and X. The task is to find the index of the array that would be visited in Kth operation. Considering the 0th index visited in first operation, the operation for visiting the rest of the indices which is to be performed (N-1) times is:

  • Let L = index of element visited last time and a variable j = (L+X)%N. 
  • Keep replacing j by (j+1)%N till such j is found that was not visited. Mark the index j as visited.

Examples :

Input: N=4, A=0, 1, 2, 3, X=2, K=4
Output: 3
Explanation: In 1st operation, index 0 is visited. 
In operation 2, as 0 is the index visited last time. So, L=0 and hence j = (0+2)%4 = 2. Since index 2 was not visited before. Mark it as visited. 
In 3rd operation, j = (2+2)%4 = 0. Since 0th index is already visited, we update j as (0+1)%4 = 1. We mark 1 as visited.
In 4th operation, j = (1+2)%4 = 3. Mark 3rd index as visited. So, after 3 operations 3rd index would be visited.

Input: N=8, A=0, 1, 2, 3, 4, 5, 6, 7, X = 8, K = 5
Output: 2

Naive Approach:

A simple approach to solve the problem would be to keep performing the operation as said in the problem.

Time Complexity: O(N)
Auxiliary Space: O(1)

Efficient Approach:

The problem can be solved based on the following observation:

Let X and Y be 2 positive integers having their gcd Z. Let X = xZ and Y=yZ. Then the integers Y%X, 2Y%X … (x-1)Y%X contain 0, Z, 2Z…(x-1)Z each exactly once. For example consider X=12 and Y = 9, Z = 3 and z = 4, y = 3. So, 0, Y%X, 2Y%X, 3Y%X are 0, 9, 6 and 3. i.e. it can be seen all multiples of Z between 0 and X have occurred exactly once.

Hence it can be seen:

  • The index that would be visited in ith operation  = (i-1)X%N. 
  • The index that would be visited in (x+i)th operation  = 1+((i-1)X%N)
  • Following the same pattern, Kth index to be visited would be (K-1)/x + ((K-1)X%N). (x is the number of multiples of gcd of X and N from 0 to N).

Following are the steps for the above approach:

  • Decrement the value of K by 1, as 1st operation is already done i.e. 0th index is already visited.
  • Initialize a variable say gcd and compute the gcd of N and X.
  • Initialize a variable say x and find the value of x which is the number of multiples of gcd of X and N from 0 to N, x = N/gcd.
  • Calculate the answer using the derived formula, answer = X*K%N + K/x.

Below is the implementation of the above approach.

C++

  

#include <bits/stdc++.h>

using namespace std;

#define ll long long

  

ll solve(ll N, ll A[], ll K, ll X)

    

    

    

    K--;

  

    

    ll gcd = __gcd(N, X);

  

    

    

    ll x = N / gcd;

    ll answer = (long long)X * K % N + K / x;

  

    

    return answer;

  

int main()

    ll N = 4, X = 2, K = 4;

    ll A[] = 0, 1, 2, 3 ;

  

    

    ll answer = solve(N, A, K, X);

    cout << answer << endl;

    return 0;

Time Complexity : O(log(min(X, N)))
Auxiliary Space : O(1)



#Approach, #Code, #Container, #DSA, #Explanation, #GCDLCM, #It, #Mathematical, #Namespace, #Read, #Responsive, #REST, #Solve, #Space, #Table, #Time, #TimeComplexity
Published on The Digital Insider at https://bit.ly/3G6vuPO.

Comments

Post a Comment

Comments are moderated.