Categories
General

Element Swapping Facebook

Element SwappingGiven a sequence of n integers arr, determine the lexicographically smallest sequence which may be obtained from it after performing at most k element swaps, each involving a pair of consecutive elements in the sequence.Note: A list x is lexicographically smaller than a different equal-length list y if and only if, for the earliest index at which the two lists differ, x’s element at that index is smaller than y’s element at that index.

Signature

int[] findMinArray(int[] arr, int k)

Input

n is in the range [1, 1000]. Each element of arr is in the range [1, 1,000,000]. k is in the range [1, 1000].

Output

Return an array of n integers output, the lexicographically smallest sequence achievable after at most k swaps.

Example 1

n = 3 k = 2 arr = [5, 3, 1] output = [1, 5, 3]We can swap the 2nd and 3rd elements, followed by the 1st and 2nd elements, to end up with the sequence [1, 5, 3]. This is the lexicographically smallest sequence achievable after at most 2 swaps.

Example 2

n = 5 k = 3 arr = [8, 9, 11, 2, 1] output = [2, 8, 9, 11, 1]We can swap [11, 2], followed by [9, 2], then [8, 2].

   function findMinArray(array $arr, int $k) : array
  {
    #arr = [5, 3, 1]
    # k:2, 1
    while($k >= 1) 
    {
    
      # swapping
      $temp = $arr[$k];        # temp 1      ; 1
      $arr[$k] = $arr[$k - 1]; # $arr[2] = 3; $arr[1] = 5
      $arr[$k - 1] = $temp;    # $arr[1] = 1; $arr[0] = 1

      #arr = [5, 1, 3]
      #arr = [1, 5, 3]
      $k--; #1 #0
    }
    
    return $arr;
    
  }

Categories
General

Slow Sums Facebook

Suppose we have a list of N numbers, and repeat the following operation until we’re left with only a single number: Choose any two numbers and replace them with their sum. Moreover, we associate a penalty with each operation equal to the value of the new number, and call the penalty for the entire list as the sum of the penalties of each operation.For example, given the list [1, 2, 3, 4, 5], we could choose 2 and 3 for the first operation, which would transform the list into [1, 5, 4, 5] and incur a penalty of 5. The goal in this problem is to find the highest possible penalty for a given input.Signature: int getTotalTime(int[] arr)Input: An array arr containing N integers, denoting the numbers in the list.Output format: An int representing the highest possible total penalty.Constraints: 1 ≤ N ≤ 10^6 1 ≤ Ai ≤ 10^7, where *Ai denotes the ith initial element of an array. The sum of values of N over all test cases will not exceed 5 * 10^6.Example arr = [4, 2, 1, 3] output = 26First, add 4 + 3 for a penalty of 7. Now the array is [7, 2, 1] Add 7 + 2 for a penalty of 9. Now the array is [9, 1] Add 9 + 1 for a penalty of 10. The penalties sum to 26.


# int1 + int2
  #  [4, 2, 1, 3]
  # [7, 2, 1] penalty 7
  # [9, 1] penalty 7 + 9 = 16
  # 10 penalty 7 + 9 = 16 + 10 = 26
  
  #highest penalty
  
  
  #  [4, 2, 1, 3]
  # [5, 2, 3] penalty 5
  # [7,3] penalty 5 + 7 = 12
  # 10 penalty  5 + 7 = 12 + 10 = 22
  
  function getTotalTime(array $arr) : int 
  {
  $penalty = 0;
    $heap = new SplMaxHeap();
    
    # array(4, 2, 1, 3)
    foreach ($arr as $value) 
    {
      $heap->insert($value);
    }
    #heap  4,3,2,1
    
    
    while ($heap->count() > 1) # count 4; 3
    {
      $int1 = $heap->extract(); # 4 ; 7 ; 9
      $int2 = $heap->extract(); # 3 ; 2 ; 1
      $sum = ($int1 + $int2);   # 7 ; 9 ; 10
      $penalty +=  $sum;         # 7; 7+9=16;16+10 = 26 
      $heap->insert($sum);      # 7,2,1 ; 9,1; 10
    }
    
    return $penalty; #26
}

Categories
General

Median Stream Facebook

You’re given a list of n integers arr[0..(n-1)]. You must compute a list output[0..(n-1)] such that, for each index i (between 0 and n-1, inclusive), output[i] is equal to the median of the elements arr[0..i] (rounded down to the nearest integer).The median of a list of integers is defined as follows. If the integers were to be sorted, then:

  • If there are an odd number of integers, then the median is equal to the middle integer in the sorted order.
  • Otherwise, if there are an even number of integers, then the median is equal to the average of the two middle-most integers in the sorted order.

Signature

int[] findMedian(int[] arr)

Input

n is in the range [1, 1,000,000]. Each value arr[i] is in the range [1, 1,000,000].

Output

Return a list of n integers output[0..(n-1)], as described above.

Example 1

n = 4 arr = [5, 15, 1, 3] output = [5, 10, 5, 4]The median of [5] is 5, the median of [5, 15] is (5 + 15) / 2 = 10, the median of [5, 15, 1] is 5, and the median of [5, 15, 1, 3] is (3 + 5) / 2 = 4.

Example 2

n = 2 arr = [1, 2] output = [1, 1]The median of [1] is 1, the median of [1, 2] is (1 + 2) / 2 = 1.5 (which should be rounded down to 1).


 function findMedian(array $arr) : array
  {
      # initialization variables
      $endWindowPosition = 0;
      $output = [];
      $maxHeap = new SplMaxHeap();
  
      # iterate throug ARR
      foreach ($arr as $key => $value) # key 0,1,2,3 ; value 5,15,1,3
      {
          # detect is_odd_number
          $isEvenNumber = false;
          if ((($endWindowPosition + 1) % 2) === 0) 
          {
            $isEvenNumber = true;
              //var_dump($endWindowPosition);
          }    

          # $endWindowPosition : 0 -> $isEvenNumber: false
          # $endWindowPosition : 1 -> $isEvenNumber: true


          # building output
          if($key === 0) 
          {
            $output[] = $value; # output[5]
          }

          # EVEN
          if ($key > 0 && $isEvenNumber === true) 
          {
             # build temp arr1
              for ($i = 0; $i <= $endWindowPosition; $i++) 
              {
                $arrEvenNumber[] = $arr[$i];
              }
              # $arrEvenNumber[5,15]
              # $arrEvenNumber[5,15,1,3]
              sort($arrEvenNumber); # $arrOddNumber[1,3 5,15]
              
              $mediumIndex = floor(($endWindowPosition + 1) / 2); #1, 1
              $int1 = $arrEvenNumber[$mediumIndex - 1 ]; # 5, 3
              $int2 = $arrEvenNumber[$mediumIndex ]; # 15 ,5        
              
              $median = floor(($int1 + $int2) / 2); # 5+15 / 2 === 10 # 3 + 5 / 2 = 4
              
              $output[] = $median; #output[5, 10]; #output[5, 10, 5,4]
              $arrEvenNumber =  [];
          }

          # ODD
         if(($key > 0) && ($isEvenNumber === false)) {
             //var_dump($endWindowPosition);
           # build temp arr1
            for ($i = 0; $i <= $endWindowPosition; $i++) 
            {
              $arrOddNumber[] = $arr[$i]; # $arrOddNumber[5,15,1]
            }
            sort($arrOddNumber); # $arrOddNumber[1, 5,15]
            $mediumIndex = floor($endWindowPosition  / 2);
            // var_dump($endWindowPosition);
            $intOddMedian = $arrOddNumber[$mediumIndex]; # 5
            $output[] = $intOddMedian; # output[5, 10, 5]
             $arrOddNumber = [];
         }
       $endWindowPosition++; # 1, 2, 3
      }    
     
    
      return $output; 

  }
Categories
General

Largest Triple Products Facebook

Largest Triple ProductsYou’re given a list of n integers arr[0..(n-1)]. You must compute a list output[0..(n-1)] such that, for each index i (between 0 and n-1, inclusive), output[i] is equal to the product of the three largest elements out of arr[0..i] (or equal to -1 if i < 2, as arr[0..i] then includes fewer than three elements).Note that the three largest elements used to form any product may have the same values as one another, but they must be at different indices in arr.

Signature

int[] findMaxProduct(int[] arr)

Input

n is in the range [1, 100,000]. Each value arr[i] is in the range [1, 1,000].

Output

Return a list of n integers output[0..(n-1)], as described above.

Example 1

n = 5 arr = [1, 2, 3, 4, 5] output = [-1, -1, 6, 24, 60]The 3rd element of output is 3*2*1 = 6, the 4th is 4*3*2 = 24, and the 5th is 5*4*3 = 60.

Example 2

n = 5 arr = [2, 1, 2, 1, 2] output = [-1, -1, 4, 4, 8]The 3rd element of output is 2*2*1 = 4, the 4th is 2*2*1 = 4, and the 5th is 2*2*2 = 8.


function findMaxProduct($arr) {
  // Write your code here
     $heap = new SplMaxHeap();
        $result = [-1, -1];
        $n = count($arr);
        

        for($i = 0; $i <= $n - 3; $i++)
        {
            $product = slidingWindowProduct($i, $arr, $heap);
            $result[] = $product;
        }
        
        
        return $result;
    }
    
     function slidingWindowProduct($strartIndex, $arr, &$heap)  
    {
        $product = 1;
        if($strartIndex == 0) {
            for($i = $strartIndex; $i <= $strartIndex + 2; $i++) 
            {
                $heap->insert($arr[$i]);
            }            
        } 
        else 
        {
            $heap->insert($arr[$strartIndex + 2]);
        }

        
        for($i=0; $i < 3; $i++) 
        {
            $value = $heap->extract();
            $temp[] = $value;
            $product *= $value;
        }


        while(count($temp) > 0) 
        {
            $val = array_shift($temp);
            $heap->insert($val);
        }
        
        return $product; #6
    }
class solution {
    
    public function __construct(){}
    
    public function findMaxProduct(array $arr) : array
    {
        $heap = new SplMaxHeap();
        $result = [-1, -1];
        $n = count($arr);
        

        for($i = 0; $i <= $n - 3; $i++)
        {
            $product = $this->slidingWindowProduct($i, $arr, $heap);
            $result[] = $product;
        }
        
        
        return $result;
    }
    
    private function slidingWindowProduct($strartIndex, $arr, &$heap) : mixed 
    {
        $product = 1;
        if($strartIndex == 0) {
            for($i = $strartIndex; $i <= $strartIndex + 2; $i++) 
            {
                $heap->insert($arr[$i]);
            }            
        } 
        else 
        {
            $heap->insert($arr[$strartIndex + 2]);
        }

        
        for($i=0; $i < 3; $i++) 
        {
            $value = $heap->extract();
            $temp[] = $value;
            $product *= $value;
        }


        while(count($temp) > 0) 
        {
            $val = array_shift($temp);
            $heap->insert($val);
        }
        
        return $product; #6
    }
}


$arr_1 = array(1, 2, 3, 4, 5);
$arr_2 = array(2, 4, 7, 1, 5, 3);


$solution = new Solution();
$res =  $solution->findMaxProduct($arr_2);
var_dump($res);
Categories
General

Minimum Length Substrings

You are given two strings s and t. You can select any substring of string s and rearrange the characters of the selected substring. Determine the minimum length of the substring of s such that string t is a substring of the selected substring.Signature int minLengthSubstring(String s, String t)Inputs and t are non-empty strings that contain less than 1,000,000 characters eachOutput Return the minimum length of the substring of s. If it is not possible, return -1Examples = “dcbefebce” t = “fd” output = 5Explanation: Substring “dcbef” can be rearranged to “cfdeb”, “cefdb”, and so on. String t is a substring of “cfdeb”. Thus, the minimum length required is 5.

Facebook Solution

function minLengthSubstring($s, $t) {
  // Write your code here
       $s1 = str_split($s);
        $t1 = str_split($t);
        $hashmap = [];
        $countLengthSubstring = 1;
        $startingcounting = false;
        
        foreach ($t1 as $character) {
            $hashmap[$character] += 1;
        }
        
        foreach ($s1 as $character1) {
            if(array_key_exists($character1, $hashmap )) {
                if($startingcounting == false) {
                    $startingcounting = true;                
                }
                $hashmap[$character1] -= 1;
                if($hashmap[$character1] <= 0){
                    unset($hashmap[$character1]);       
                }
            }
            
            if(count($hashmap) == 0) {
                return $countLengthSubstring;
            }
            
            if($startingcounting) {
                $countLengthSubstring++;
            }
        }
        return -1;
  
}  

Clean

class solution {
    
    public function __construct() {}
    public function minLengthSubstring(string $s11, string $t11) 
    {
        $s1 = str_split($s11);
        $t1 = str_split($t11);
        $hashmap = [];
        $countLengthSubstring = 1;
        $startingcounting = false;
        
        foreach ($t1 as $character) {
            $hashmap[$character] += 1;
        }
        
        foreach ($s1 as $character1) {
            if(array_key_exists($character1, $hashmap )) {
                if($startingcounting == false) {
                    $startingcounting = true;                
                }
                $hashmap[$character1] -= 1;
                if($hashmap[$character1] <= 0){
                    unset($hashmap[$character1]);       
                }
            }
            
            if(count($hashmap) == 0) {
                return $countLengthSubstring;
            }
            
            if($startingcounting) {
                $countLengthSubstring++;
            }
        }
        return -1;
    }
}

// $s1 = "dcbefebce";
// $t1 = "fd";

$s1 = "bfbeadbcbcbfeaaeefcddcccbbbfaaafdbebedddf";
$t1 = "cbccfafebccdccebdd";

$solution = new Solution();
print $solution->minLengthSubstring($s1, $t1);
Categories
General

Nodes in a Subtree

You are given a tree that contains N nodes, each containing an integer u which corresponds to a lowercase character c in the string s using 1-based indexing.You are required to answer Q queries of type [u, c], where u is an integer and c is a lowercase letter. The query result is the number of nodes in the subtree of node u containing c.Signature int[] countOfNodes(Node root, ArrayList<Query> queries, String s)Input A pointer to the root node, an array list containing Q queries of type [u, c], and a string sConstraints N and Q are the integers between 1 and 1,000,000 u is a unique integer between 1 and N s is of the length of N, containing only lowercase letters c is a lowercase letter contained in string s Node 1 is the root of the treeOutput An integer array containing the response to each queryExample

        1(a)
        /   \
      2(b)  3(a)

s = “aba” RootNode = 1 query = [[1, ‘a’]]Note: Node 1 corresponds to first letter ‘a’, Node 2 corresponds to second letter of the string ‘b’, Node 3 corresponds to third letter of the string ‘a’.output = [2]Both Node 1 and Node 3 contain ‘a’, so the number of nodes within the subtree of Node 1 containing ‘a’ is 2.

class Node{
    public $val;
    public $children ;
    function __construct($val){
        $this->val = $val;  
        $this->children = array();
    }
}

// Add any helper functions you may need here


function countOfNodes($root, $queries, $s) {
      #initialization variables
        $countOfNodes = array();
        foreach  ($queries as $query) {
            $nodeValueToBeSearched = $query[0]; #1, 2, 3
            $countOfNodes[$nodeValueToBeSearched] = 1;
        }
        $parents = array();

        
        #mapping string
        $index = 1;   
        $hashmapString = array();
        $array_string = str_split($s);
        foreach($array_string as $character) {
            $hashmapString[$index] = $character;
                $index += 1;
       } 
        
        
        #depth first search
        dfs($root, $queries, $countOfNodes, $hashmapString, $parents);
        
        
        #create result
        foreach ($countOfNodes as $value) {
            $result[] = $value;
        }
        
        return $result;
    }
    
     function dfs($node, $queries, &$countOfNodes , $hashmapString, $parents) 
    {
 
        
        #populate countOfNodes
        foreach  ($queries as $query) {
            $nodeValueToBeSearched = $query[0]; #1, 2, 3
            $letterToBeSearched = $query[1];    #a, b, a
            


            if ($hashmapString[$node->val] === $letterToBeSearched) {
                if (in_array($nodeValueToBeSearched, $parents)){
                    $countOfNodes[$nodeValueToBeSearched] += 1; 


                    #$countOfNodes[1] = 1+1+1
                    #$countOfNodes[2] = 1
                }
            }            
        }
        
        #exit condition
        if(empty($node->children)){
            return;
        }
        
        
        #populating visit array
        foreach($node->children as $childNode) {
            $visit[] = $childNode;
        }
        $parents[] = $node->val;
        
        while (count($visit) > 0) {
            $nodeChild = array_shift($visit);
            
            dfs($nodeChild, 
                       $queries, 
                       $countOfNodes, 
                       $hashmapString, 
                        $parents
                      );
        }
        
        
    }
Categories
General

Number of Visible Nodes Facebook

There is a binary tree with N nodes. You are viewing the tree from its left side and can see only the leftmost nodes at each level. Return the number of visible nodes.Note: You can see only the leftmost nodes, but that doesn’t mean they have to be left nodes. The leftmost node at a level could be a right node.Signature int visibleNodes(Node root) {Input The root node of a tree, where the number of nodes is between 1 and 1000, and the value of each node is between 0 and 1,000,000,000Output An int representing the number of visible nodes.Example

            8  <------ root
           / \
         3    10
        / \     \
       1   6     14
          / \    /
         4   7  13            

output = 4

<?php

// Add any extra import statements you may need here


class TreeNode{
  public $val;
  public $left;
  public $right;
  public function __construct($val=0) {
    $this->val = $val;
    $this->left = NULL;
    $this->right = NULL;
  }
}

// Add any helper functions you may need here


function visibleNodes($root) {
        $result = [];
        
        $numberVisibleNode = 1;
 
        dfs($root, $result, $numberVisibleNode);
       
        return  max($result);;
    }
    
     function dfs(TreeNode $currentNode, array &$result,$numberVisibleNode )  {
        if(($currentNode->left === null)  && ($currentNode->right === null)) {
                   
           // var_dump($currentNode->val.' '.$numberVisibleNode);
            $result[$currentNode->val] = $numberVisibleNode;
            return ;
        }
        
        if($currentNode->left != null) {
          //  var_dump('leftside '.$currentNode->val.' '.$numberVisibleNode);
            $numberVisibleNodeLeft = $numberVisibleNode;
            $numberVisibleNodeLeft++; #2
            dfs($currentNode->left, $result, $numberVisibleNodeLeft);
        }
        
        if(($currentNode->right !== null)) {
           // var_dump('righttside '.$currentNode->val.' '.$numberVisibleNode);
            $numberVisibleNodeRight = $numberVisibleNode;
            $numberVisibleNodeRight++;#5,
            dfs($currentNode->right, $result, $numberVisibleNodeRight);
        }
    }

Categories
General

Reverse to Make Equal Facebook

Given two arrays A and B of length N, determine if there is a way to make A equal to B by reversing any subarrays from array B any number of times.Signature bool areTheyEqual(int[] arr_a, int[] arr_b)Input All integers in array are in the range [0, 1,000,000,000].Output Return true if B can be made equal to A, return false otherwise.Example A = [1, 2, 3, 4] B = [1, 4, 3, 2] output = trueAfter reversing the subarray of B from indices 1 to 3, array B will equal array A.

function areTheyEqual($s, $t) {
  
  // Write your code here
  $arr_a = $s;
  $arr_b = $t;
  
  $isEqual = false;
            $hashMapArrayA = array();
            $hashMapArrayB = array();

            #sanity check 
            $sizeArr_a = count($arr_a); #4
            $sizeArr_b = count($arr_b); #4
            if ($sizeArr_a !== $sizeArr_b)
            {
                return false;

            }
            
            #building hashMapA
            #hashMapA[1] = 1
            #hashMapA[2] = 1
            #hashMapA[3] = 1
            #hashMapA[4] = 1
            foreach ($arr_a as $key => $value) {
                if(array_key_exists($value, $hashMapArrayA)){
                    $hashMapArrayA[$value] = $hashMapArrayA[$value] + 1;     
                } else {
                    $hashMapArrayA[$value] = 1;
                }
            }



            #building hashMapB
            #hashMapB[1] = 1
            #hashMapB[2] = 1
            #hashMapB[3] = 1
            #hashMapAB[4] = 1

            foreach ($arr_b as $key => $value) {
                if(array_key_exists($value, $hashMapArrayB)){
                    $hashMapArrayB[$value] = $hashMapArrayB[$value] + 1;     
                } else {
                    $hashMapArrayB[$value] = 1;
                }
            }

            
            #sanity check 
            $sizehashMapArrayB = count($hashMapArrayB); #4
            $sizehashMapArrayA = count($hashMapArrayA); #4
            if ($sizehashMapArrayA !== $sizehashMapArrayB)
            {
                return false;
            }
            

            foreach($hashMapArrayA as $key => $valueA) {
                #hashMapA[1] exist
                #hashMapA[1] == hashMapB[1] equals
                #hashMapA[1] exist
                #hashMapA[1] == hashMapB[1] equals

                if(!array_key_exists($key, $hashMapArrayB))
                {
                    return false;
                }
                    
                if ($hashMapArrayA[$key] !== $hashMapArrayA[$key]) 
                {
                    return false;;
                 }

            }
            
                foreach($hashMapArrayB as $key => $valueB) {
                #hashMapA[1] exist
                #hashMapA[1] == hashMapB[1] equals
                #hashMapA[1] exist
                #hashMapA[1] == hashMapB[1] equals
                    


                if(!array_key_exists($key, $hashMapArrayA))
                {
                    return false;
                }
                    
                if ($hashMapArrayB[$key] !== $hashMapArrayA[$key]) 
                {
                    return false;;
                 }
            }
            

  
            $isEqual = true;
            return $isEqual;
}  
Categories
General

Passing Yearbooks Facebook

There are n students, numbered from 1 to n, each with their own yearbook. They would like to pass their yearbooks around and get them signed by other students.You’re given a list of n integers arr[1..n], which is guaranteed to be a permutation of 1..n (in other words, it includes the integers from 1 to n exactly once each, in some order). The meaning of this list is described below.Initially, each student is holding their own yearbook. The students will then repeat the following two steps each minute: Each student i will first sign the yearbook that they’re currently holding (which may either belong to themselves or to another student), and then they’ll pass it to student arr[i-1]. It’s possible that arr[i-1] = i for any given i, in which case student i will pass their yearbook back to themselves. Once a student has received their own yearbook back, they will hold on to it and no longer participate in the passing process.It’s guaranteed that, for any possible valid input, each student will eventually receive their own yearbook back and will never end up holding more than one yearbook at a time.You must compute a list of n integers output, whose element at i-1 is equal to the number of signatures that will be present in student i’s yearbook once they receive it back.

Signature

int[] findSignatureCounts(int[] arr)

Input

n is in the range [1, 100,000]. Each value arr[i] is in the range [1, n], and all values in arr[i] are distinct.

Output

Return a list of n integers output, as described above.

Example 1

  • Student 1 signs their own yearbook. Then they pass the book to the student at arr[0], which is Student 2.
  • Student 2 signs their own yearbook. Then they pass the book to the student at arr[1], which is Student 1.

n = 2 arr = [2, 1] output = [2, 2]Pass 1:

Pass 2:

  • Student 1 signs Student 2’s yearbook. Then they pass it to the student at arr[0], which is Student 2.
  • Student 2 signs Student 1’s yearbook. Then they pass it to the student at arr[1], which is Student 1.

Pass 3:

  • Both students now hold their own yearbook, so the process is complete.

Each student received 2 signatures.

Example 2

n = 2 arr = [1, 2] output = [1, 1]Pass 1:

  • Student 1 signs their own yearbook. Then they pass the book to the student at arr[0], which is themself, Student 1.
  • Student 2 signs their own yearbook. Then they pass the book to the student at arr[1], which is themself, Student 2.

Pass 2:

  • Both students now hold their own yearbook, so the process is complete.

function findSignatureCounts($arr) {
  foreach ($arr as $index => $studentNumber) {
   //   var_dump('Book for student '.$studentNumber);

    $bookedSigned[$studentNumber] = [$studentNumber];
  
    dfs($arr[$studentNumber - 1], $studentNumber, $index, $bookedSigned, $arr);
    
    $result[] = count($bookedSigned[$studentNumber] );
   
    
}

//var_dump('$result');
//var_dump($result);

  return $result;


  
}



function dfs($newStudentNumber, $studentNumber, $studentIndex, &$bookedSigned, $arr) {
    if(in_array($newStudentNumber, $bookedSigned[$studentNumber])){
        return;        
    }
    $bookedSigned[$studentNumber][] = $newStudentNumber;
     // var_dump( 'for student '.$studentNumber.' Book signed by');
    //  var_dump($bookedSigned[$studentNumber] );
    
    if(($studentNumber - 1) < 0) {
        return;        
    }



     dfs($arr[$newStudentNumber - 1], $studentNumber, $studentIndex, $bookedSigned, $arr);
}

Categories
General

Rotational Cipher Facebook

One simple way to encrypt a string is to “rotate” every alphanumeric character by a certain amount. Rotating a character means replacing it with another character that is a certain number of steps away in normal alphabetic or numerical order.For example, if the string “Zebra-493?” is rotated 3 places, the resulting string is “Cheud-726?”. Every alphabetic character is replaced with the character 3 letters higher (wrapping around from Z to A), and every numeric character replaced with the character 3 digits higher (wrapping around from 9 to 0). Note that the non-alphanumeric characters remain unchanged.Given a string and a rotation factor, return an encrypted string.

Signature

string rotationalCipher(string input, int rotationFactor)

Input

1 <= |input| <= 1,000,000 0 <= rotationFactor <= 1,000,000

Output

Return the result of rotating input a number of times equal to rotationFactor.

Example 1

input = Zebra-493? rotationFactor = 3 output = Cheud-726?

Example 2

input = abcdefghijklmNOPQRSTUVWXYZ0123456789 rotationFactor = 39 output = nopqrstuvwxyzABCDEFGHIJKLM9012345678

function rotationalCipher($input, $rotation_factor) {
  
            for($i=0; $i< 26;$i++) {
              $letter = chr(97 + $i);
              $alphabetMap[$letter] = $i;
          }   
   
        $newString = '';
        $input = str_split($input);
        foreach ($input as $item) {
            #Da
            //Sanity Check
            if(!ctype_alpha($item) && !is_numeric($item))
            {
                 $newString .= $item;
            }
            //if character
            if(ctype_alpha($item))
            {
                #item D;a
                $initialstateUpperCase = false; 
                if (ctype_upper($item)) {
                    $initialstateUpperCase = true; #D
                    $item = strtolower($item);  #d
                }
                
                $value = $alphabetMap[$item]; #3;0
                $newValue = $value + $rotation_factor; #5;2
                if($newValue > 26) {
                    $newValue = $newValue % 26;
                }
                $newCharacter = array_search($newValue, $alphabetMap); #f;c
                if($initialstateUpperCase === true)
                {
                    $newCharacter = strtoupper($newCharacter);    #F
                }
            
                $newString .= $newCharacter; #Fc
            }
            
            
            //if integer
            if(is_numeric($item))
            {
                $newValue = $item + $rotation_factor;
                if($newValue > 10) {
                    $newValue = $newValue % 10;
                }
                $newString .= $newValue;
            }
        }
            return $newString;            
  
  
}