First Capital Using Recursion

CONCEPTS USED:

Recursion

DIFFICULTY LEVEL:

Easy

PROBLEM STATEMENT(SIMPLIFIED):

Given a String T, find the 1st occurrence of the capital (uppercase) alphabet. Print its index if present, else -1.

See original problem statement here

For Example:

Input : T = prepBytes

Output : 4
Input : T = helloWorld

Output : 5

Can we use Recursion here ?

Yes, the problem can be divided into sub problems, for example T = "prepBytes",
check if first character is Upper Case. If Yes print index else search in the remaining string by referring some websites to learn programming.

SOLVING APPROACH:

  1. Create a function with three parameters a string, start index, end index.

  2. Base conditions form the Backbone of recursion, so if start becomes greater than end, simply return -1.

  3. Because this implies entire string has been traversed but no upper case letter was found.

  4. If the Ascii value of current char is greater than or equal to 65 and less than or equal to 90, this means an upper case letter is found, simply return this index value.

ALGORITHM:

IsUpperCase(string, i, j)

  if (entire string is traversed or i becomes greater than j)
    return -1

  if (character at ith index is upper case)
    return i
  else
    return IsUpperCase(string, i+1, j)

SOLUTIONS:


#include 

int first_upper(char s[],int i){
  if(s[i] == '\0')                   //base condition
    return -1;
  if(s[i] >= 65 && s[i] <=90)
    return i;
  else
    return first_upper(s,i+1);
}
int main()
{
  int n;
  scanf("%d",&n);
  while(n--){
    char s[100000];
    scanf("%s",s);
    printf("%d\n",first_upper(s,0));

  }
  return 0; 
}

#include <bits/stdc++.h>
using namespace std;

int first_upper(string s,int first,int last){

  if(first>last)       //base condition
    return -1;
  if(s[first] >= 65 && s[first] <= 90)
    return first;
  else
    return first_upper(s,first+1,last);
}
int main()
{
  int n;cin>>n;
  while(n--){
    string s;cin>>s;
    int first = 0;
    int last = s.size()-1;
    cout<<first_upper(s,first,last)<<"\n";
  }
  return 0;
}


import java.util.*;
import java.io.*;

public class Main {

  static int first_upper(String s,int first){
  if(first >= s.length())          //base condition
    return -1;
  if (Character.isUpperCase(s.charAt(first)))  
      return first;
  else
    return first_upper(s,first+1);
  }

  public static void main(String args[]) throws IOException {

    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    while(n!=0){
      String s = sc.next();
      int first = 0;
      System.out.println(first_upper(s,first));
      n--;
    }
  }
}

Previous post Total number of ways to form a team of size K from X men and Y women with at least 4 men and 1 woman in the team
Next post Arrange Ways

Leave a Reply

Your email address will not be published. Required fields are marked *