Sparse Arrays Hackerrank problem solution

Sparse Arrays Hackerrank

There are N strings. Each string’s length is no more than 20 characters. There are also Q queries. For each query, you are given a string, and you need to find out how many times this string occurred previously.

Input Format

The first line contains N, the number of strings.
The next N lines each contain a string.
The N+2nd line contains Q, the number of queries.
The following Q lines each contain a query string.

Constraints

1<=N<=1000 1<=Q<=1000 1<=length of any string <=20 Sample Input

4
aba
baba
aba
xzxb
3
aba
xzxb
ab

Sample Output

2
1
0

Explanation

Here, “aba” occurs twice, in the first and third string. The string “xzxb” occurs once in the fourth string, and “ab” does not occur at all.

Solution

The approach is fairly simple. Store all the strings that come in as input in an array of strings(character arrays). For each query search the entire input and check which all strings are equal to the current string by using strcmp and increment the answer accordingly.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {

public static void main(String[] args) {
   Scanner sc=new Scanner(System.in); 
      int n=sc.nextInt();
      String []s=new String[n];   
      int count=0;
     for(int i=0;i<n;i++)
        {
          sc.nextLine();
           s[i]=sc.next();
        }   
    int n1=sc.nextInt();
    String[] s1=new String[n1];
    for(int j=0;j<n1;j++)
        {
           sc.nextLine();
           s1[j]=sc.next();  
      }
   for(int i=0;i<n1;i++)
       {
          count=0;
          for(int j=0;j<n;j++)
              {
                 if((s[j].equals(s1[i])))
                     {
                     count++;
                    }

              }
         System.out.println(count);
      }


}


}
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <cassert>

using namespace std;

char inp[1002][25];

int main()
{
    int n, q;
    cin>>n;
    for(int i = 0 ; i< n; i++)
    {
        cin>>inp[i];
        assert(strlen(inp[i]) >= 1 && strlen(inp[i]) <= 20);
    }
    char check[25];
    cin>>q;
    while(q--)
    {
        cin>>check;
        assert(strlen(check) >= 1 && strlen(check) <= 20);
        int ans = 0;
        for(int i = 0 ; i < n; i++)
        {
            if(strcmp(inp[i], check) == 0)
                ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}
#include <iostream>
#include <string>

using namespace std;

const int N = int(1e3) + 100;

string x[N];
int cnt[N], sz = 0;

void add(string s) {
  for (int i = 0; i < sz; i++) {
    if (x[i] == s) {
      cnt[i] += 1;
      return;
    }
  }
  cnt[sz] = 1;
  x[sz++] = s;
}

int query(string s) {
  for (int i = 0; i < sz; i++) {
    if (x[i] == s) {
      return cnt[i];
    }
  }
  return 0;
}

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    add(s);
  }
  int q;
  cin >> q;
  for (int i = 0; i < q; i++) {
    string s;
    cin >> s;
    cout << query(s) << '\n';
  }
  return 0;
}

 CodePair
 hasectic 
No task has been added yet
Scratchpad
 
Question 1
 
Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Enter your code here. Read input from STDIN. Print output to STDOUT
n = int(raw_input())
arr=[]
for i in range(n):
    arr.append(raw_input())
m = int(raw_input())
for i in range(m):
    query=raw_input()
    count=0
    for i in range(n):
        if query==arr[i]:
            count+=1
    print count
    
    
Stdin 
Stdout 
Run Code
 Chat
 

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

Leave a reply:

Your email address will not be published.