We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Construct the Array
  5. Discussions

Construct the Array

Sort by

recency

|

166 Discussions

|

  • gbednik
     + 0 comments
    const long divide = pow(10, 9) + 7;

    // Return the number of ways to fill in the array.
long countArray(int n, int k, int x) 
{
    if (n == 3)
    {
        if (x == 1)
            return long(k-1)%divide;
        else
            return long(k-2)%divide;   
    }
    else
    {
				// Array of answers for various n and x=1
        vector<long> A;
				// Array of answers for various n and x!=1 (does not depend on specifica value of x)
        vector<long>B;
        
        A.reserve(n-2);
        B.reserve(n-2);
        
				// special case n=3
        A.push_back((k-1)%divide);
        B.push_back((k-2)%divide);
        
				// increase n by 1 recurrently
        for(int i = 0 ; i < n-3 ; i++)
        {
            long a = (k-1)*B.back();
            long b = A.back() + (k-2)*B.back();
            a = a % divide;
            b = b % divide;
            A.push_back(a);
            B.push_back(b);
        }
        if(x == 1)
            return A.back();
        else
            return B.back();
    }

}

  • dunghva1ts42003
     + 0 comments

    public static long countArray(int n, int k, int x) { long mode = 1000000000 + 7; long[][] dp = new long[n + 1][2]; if (n == 2) { if (x == 1) return 0; else return 1; } if (x != 1) { dp[2][0] = 1; dp[2][1] = k - 2; } else { dp[2][0] = 0; dp[2][1] = k - 1; } for (int i = 3; i <= n; i++) { dp[i][0] = dp[i - 1][1] % mode; dp[i][1] = (dp[i - 1][1] * (k - 2) + dp[i - 1][0] * (k - 1)) % mode; }

        return dp[n][0];
}

  • chunsh10
     + 0 comments

    I don't know where this code is wrong. I modularized it, but the answer is different.

    static long mod(long x){
    while(x<0)
        x+=1000000007;
    return (x%1000000007);    
}
public static long countArray(int n, int k, int x)
{
// Return the number of ways to fill in the array.
    if(k<=1 || n<2)return 0;
    if(k==2 && n<=3) return 0;
    if(k==2)
    {
        if(x==1 ) 
        {
            if( n%2==0)  return 0;
            return 1;
        }
        if(x==2)
        {
            if( n%2==1)  return 0;
            return 1;
        }
    }

    long result= 1;
    int N=n-2;

    for(int i=0;i<N;i++)
    {
        result = mod(result*(k-1));
    }
    //result=mod(result*k);
    Console.WriteLine("result : "+result);
    long kn=1;
    for(int i=0;i<N-1;i++)
    {
        kn = mod(kn*(k-1));
    }
    Console.WriteLine("kn : "+kn);
    //result=mod(result-2*kn);
    Console.WriteLine("result : "+result);
    long ss1=0;
    long ss2=0;

        ss1 =mod(((kn+(k-1)*(((N-1)%2==0)?1:-1))/k));
        ss2 =mod(((kn+(((N)%2==0)?1:-1))/k));
    if(x==1)
    {
        kn=mod(ss2*(k-1));
    Console.WriteLine("ss1 : "+kn);
    }
    else 
    {
        kn=mod(ss2*(k-2)+ss1);
    Console.WriteLine("ss2 : "+kn);
    }
    return mod(result -kn);
}

  • shanefostersmith
     + 0 comments

    For an O(n) time and O(1) space complexity, we can think of this problem as keeping track of the total combinations depending on whether we placed an X value previously or we didn't (from n = 3 to n - 2). At n = 2, we either had [1,X] or [1, not X and not 1] if X != 1, or [1,1] and [1, not 1] if X = 1; this gives us combinations of 1 and (k - 2) respectively for the X != 1 case, and 0 and (k - 1) respectively for the X = 1 case. For the iterations from 3 to n - 2, we need to update the “previous was not X” and the “previous was X” combination values. If the previous value was not X, we have two choices: place an X or don’t. If we place an X, the total combinations have not changed, therefore the new “previous was X” is just the previous “previous was not X” value. If we don’t place an X and the previous was not X, the new “previous was not X” combinations are multiplied by (k-2), since we can’t place the previous number either. Finally, we have the case where the previous was X and we don’t place an X. There are (k-1) options, so we multiply the “previous was X” value by (k-1) and add it to the new “previous was not X” value. At n - 1 position, we can never place an X. So if the n - 2 spot was an X, we have (k-1) options and if not, we have (k-2) options. Therefore, our final result will be: “previous was X” times (k-1) + “previous was not X” times (k-2). Not dynamic programming really, but intuitively makes sense. See Java solution below.

    public static long countArray(int n, int k, int x) {
        // Base Cases
        if (n == 3) {
           return (1 == x) ? k - 1 : k - 2;
        }
        if (k == 2) {
            if (1 == x) {
                return (n % 2);
            } else {
                return (n % 2 == 0) ? 1 : 0;
            }
        }
        int mod = 1000000007;
        if (n == 4) {
            if (1 == x) {
                return ((k - 1) % mod) * ((k - 2) % mod);
            } else {
                return (k-1) + ((k-2) % mod)* ((k-2) % mod);
            }
        }
        // start at position 3 and go until 2 before n
        long prevWasX;
        long prevWasNotX;
        if (1 == x) {
            prevWasNotX = k - 1;
            prevWasX = 0;
        } else {
            prevWasNotX = k - 2;
            prevWasX = 1;
        }
        // start at position 3 and go until 2 before n
        for (int i = 3; i <= n-2; i++) {
            long newPrevWasX;
            long newPrevNotX;
            // If previous was X, can place anything but X
            newPrevNotX = ((prevWasX % mod) * (k-1)) % mod;
            
            // If previous was not X, can place X or not place X
            // Do not place X or previous
            newPrevNotX += ((prevWasNotX % mod) * (k-2)) % mod;
            
            // Place X, if previous not X
            newPrevWasX = prevWasNotX % mod;
            
            // Update Counts
            prevWasNotX = newPrevNotX;
            prevWasX = newPrevWasX;
        }
        // Last Spot (before X)
        // If previous was X, can place anything but X
        long lastSpot1= ((prevWasX % mod) * (k - 1)) % mod;
        
        // If previous was not X, can place anything but X and previous
        long lastSpot2 = ((prevWasNotX % mod) * (k - 2)) % mod;
        
        return (lastSpot1 + lastSpot2) % mod;
    }

  • yash_bhat94
     + 0 comments

    Hello,

    For me the same solution is passing in python but failing in Scala, can someone help me debug it?

        if((n-2)%2==1):
        y=((((k-1)**(n-2-1))-1))//k
        if (x == 1):
            ways = ((y + 1)*(k-1))+((((k-1)*y))*(k-2))
        else:
            ways=((((k-1)*y) + 1)*(k-2))+((y)*(k-1))
    else:
        y = ((((k - 1) ** (n - 2 - 1)) + 1)) // k
        if (x == 1):
            ways = ((y - 1)*(k-1))+(((k-1)*y)*(k-2))
        else:
            ways=((((k-1)*y) - 1)*(k-2))+((y)*(k-1))

        if (n % 2 == 1) {
      val y = (scala.math.pow(k - 1, n - 3).toLong - 1) / k
      if (x == 1) {
        ((y + 1) * (k - 1)) + ((k - 1) * y * (k - 2))
      }
      else {
        ((((k - 1) * y) + 1) * (k - 2)) + (y * (k - 1))
      }
    }
    else {
      val y = (scala.math.pow(k - 1, n - 3).toLong + 1) / k
      if (x == 1) {
        ((y - 1) * (k - 1)) + ((k - 1) * y * (k - 2))
      }
      else {
        ((((k - 1) * y) - 1) * (k - 2)) + (y * (k - 1))
      }

    } % div