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

  • 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;
    }