Maximum No. Of Subarray

You are given an array $A$ of $N$ integers. Tell me the maximum number of subarrays such that all the numbers in the array having same value must be in a same subarray. 


problem taken from https://csacademy.com/contest/round-32/task/subarray-partition/

Constraints:

1≤N≤10​5​​ 

1≤A​i​​≤10​5​​

INPUT:              OUTPUT

4                           2

1 1 2 2

Explanation:

1 1 is in a subarray {1,1}

2 2 is in other subarray {2,2}

so output is 2

Solution in C:

/*

Sundar Lal Baror═╩═╦═╩═╦═╩═╦═╩═╦═╩═

█▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀█

█═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═█

█═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═█

█═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═█

█═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═█

█═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═█

█═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═█

█═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═█

█═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═█

█▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄█

*/

#include <stdio.h>

#define ll long long int 

ll max(ll a,ll b){return a>b?a:b;}

ll arr[100000];

ll arr1[100005];

int main() {

    

    ll n,i;

   // ll sum=0;

   // ll count=0;

    scanf("%lld",&n);

    for(i=1;i<=n;i++)

    {scanf("%lld",&arr[i]);

    arr1[arr[i]]=i;

       

    }

    

    ll j=1;

    ll cnt=0;

    for(i=1;i<=n;i++)

    {

        if(j<i)

        cnt++;

        j=max(j,arr1[arr[i]]);

    }

    printf("%lld\n",cnt+1);

    

    return 0;

}

 

                         Snake and Mangooes
There are snakes and mangooes in the lines and a mangooes can eat at most one  neighbour snake at a time. so there is a election on mangooes vs snakes. If there are maximum mangooes than snakes than Mangooes wins the election vice versa.
The question is taken from codechef snackdown elimination B.
URL is https://www.codechef.com/SNCKPB17/problems/SNELECT
If there are same no. of mangooes and snakes then 'tie' will be answer.
There are T testcases in input and then a string containing 's' and 'm'.

In Output If snakes wins the 'Snakes' and if mangooes wins then 'mangooes' as output. for tie simply output as 'tie'.

Input                          OutPut
4                                mangooes
sm                                tie
ssm                               tie
sms                               tie
ssmmmssss                         snakes

So code for this prolem is in C is as following:

#include<stdio.h>
#include<string.h>
int main()
{
 int t,s=0,m=0;
 char str[10000];
 scanf("%d",&t);
 while(t--)
 {
  scanf("%s",str);
  s=0;
  m=0;
  int i,j,k;
  
  int l=strlen(str);
  char pre;
  
  int c=0,f=0;
  
  for(i=0;i<l;i++)
  {
   if(str[i]=='s')
   s++;
   else
   m++;
  }
  int counter=0;
  for(i=0;i<l;i++)
  {
   
if(str[i]=='s' && str[i+1]=='m' || str[i]=='m' && str[i+1]=='s'){
    s--;
    i++;
}
   
    
   }
   //("%d %d\n",c,f); 
  }
  
  if(s==m)
  printf("tie\n");
  else if(s<m)
  printf("mongooses\n");
  else
  printf("snakes\n");
  
  
  
  
  
 }
 
 
 
 return 0;
}

Factorial Number System or factoradic

It is used for solving permutation problems. Generally with the help of this concept we can find the permutation string at Kth position.The factorial number system term was used first time by "Knuth".

Here is a code which was asked in Amazon Hiring Challenge to print the Kth permuted string.

Python code:

def result(p,ls):

    rem=[]

    z=0

    x=1

    while p!=0:

        z=p%x

        rem.append(z)

        p=p//x

        x=x+1

    rem=rem[::-1]

    rem1=list(map(int,rem))

    

    how_many=0

    if len(rem1)!=len(ls):

        how_many=len(ls)-len(rem1)

        #print(how_many)

        for go in range(how_many): 

            rem1.insert(0,0)

    g=[]

    #print(rem1)

    for l in range(len(ls)):

        v=rem1[l]

        st=ls[v]

        g.append(st)

        ls.remove(ls[v])

        #print(ls)

    return "".join(g)

t=int(input())

#print(type(t))

for i in range(t):

    strr,p=input().split()

    #print(strr) 

    P=int(p)

    ls=list(strr)

    gh=str(result(P-1,ls))

    print(gh)

  Input                         output

  1                          adbc

  abcd 5